You've got it just about right..

Change the base path directory setting in admin configuration.
Rename the installation directory to what you set the base path to.
Delete the .htaccess file in your /admin directory, and re-password protect the /admin directory.

I suspect the 404 you are seeing is caused because the corresponding htpaswd file used to authenticate access to the admin directory still points to the old directory name. You may not be able to edit that file directly.