We're using TeamCity 8.0.6 and according to the 8.x documentation, you can use the DELETE REST api to delete user:
Update/remove specific user: PUT/DELETE http://teamcity:8111/httpAuth/app/rest/users/<userLocator>
But I tried the DELETE request and I get an error:
Not supported request. Please check URL, HTTP method and transfered data are correct. metadata: [Allow:[GET,OPTIONS,HEAD,PUT],]
I tried the same REST api with 9.0.4 and it works there. Seems that there's a bug in the documentation or TeamCity 8.0.6 that the DELETE request does not work.