How to correctly remove a module in a staged environment?
Be very careful about keeping your database and code in sync; as you mention in your question, the modules to be uninstalled need to stay in the code base until their uninstall hooks are run on the live database.  This is a limitation of Drupal that a git pull workflow alone is not going to solve.

I would recommend that instead of attempting to adjust your process, you instead look for ways to reduce the downtime required to process your updates.  I would recommend setting up a ying / yang multisite staging environment to solve this problem.  n.b. I have not used the scripts contained in the preceding link; you may wish to set things up differently, following the same idea that you can swap your live and stage sites during deployment.

Continue to follow the same procedure you outlined in your question with the following adjustments:

a. Sync from dev to stage (yang) as usual. Test by doing an uninstall of the modules to be removed followed by code removal, etc.  Git workflow notes: create a tag or note the hashid of the different states of your code: all modules in place prior to uninstall, code modules removed, your overrides &amp; c. removed, etc. as needed.  Perhaps only two references are needed.

b. When testing is complete and accepted, restore the code on stage (yang) to the state of live (ying).

c. Prepare the live (ying) site for update by disabling any user's ability to change content on the system. An sql update to the permission table will usually do here. At this point, users will still be able to read content on the live site, but will get a permission denied error if they try to update content. (If you are cool, perhaps you could change the permission denied handler to print an appropriate notice that the function is temporarily unavailable).

d. Now push the live (ying) database back to stage (yang) database, excluding the permissions table from the update.

e. Repeat step a. again.  If you have your hashtags handy, it should be easy to restore to the state where the modules to be removed exist, run the uninstall hooks on the database, and then advance back to the state of the code where your items from step 1 are merged back in.

f. You are now ready to swap ying and yang. Do this by adjusting your Apache configuration directives. Note that if you do an /etc/init.d/apache restart, some connections may be dropped, but /etc/init.d/apache reload will allow for a clean swap.

g. Live is now 'yang'; the permissions table is unmodified here, so users can create content.  If you automate steps e. and f., the time unavailable should be very low.

h. Push live (yang) back to stage (ying), both code and database -- or push from dev, as needed. You now have a clean environment ready for your next iteration.