I think David Sulc's approach is the only one which ensures that you avoid requests getting through while the app is in a broken state.
It is a bit of a pain, but may be necessary in some circumstances.
As he stated, it does require that the db migrations are non-destructive.
However, it can be difficult to push your migrations and schema changes prior to the rest of the code, as the obvious approach ('git push heroku {revnum}') relies on you having checked the migrations in before the rest of the code.
If you haven't done that, it's still possible to do this using a temporary branch:
Create a branch, based at the git revision that you most recently pushed to heroku:
git branch <branchname> <revnum-or-tag>
Check out that branch:
git checkout <branchname>
If your db migration commits only contained migrations, and no code changes, cherry-pick the commits that contain the database changes:
git cherry-pick <revnum1> <revnum2>...
If you commited your db changes in revisions which also contained code changes, you can use 'git cherry-pick -n' which won't automatically commit; use 'git reset HEAD ' to remove the files that aren't db changes from the set of things that are going to be commited. Once you've got just the db changes, commit them in your temporary branch.
git cherry-pick -n <revnum1> <revnum2>...
git reset HEAD <everything that's modified except db/>
git status
... check that everything looks ok ...
git commit
Push this temporary branch to heroku (ideally to a staging app to check that you've got it right, since avoiding downtime is the whole point of jumping through these hoops)
git push heroku <branchname>:master
Run the migrations
heroku run rake db:migrate
At this point, you might think that you could just push 'master' to heroku to get the code changes across. However, you can't, as it isn't a fast-forward merge. The way to proceed is to merge the remainder of 'master' into your temporary branch, then merge it back to master, which recombines the commit histories of the two branches:
git checkout <branchname>
git merge master
git diff <branchname> master
... shouldn't show any differences, but just check to be careful ...
git checkout master
git merge <branchname>
Now you can push master to heroku as normal, which will get the rest of your code changes across.
In the second-to-last step, I'm not 100% sure whether merging master to {branchname} is necessary. Doing it that way should ensure that a 'fast-forward' merge is done, which keeps git happy when you push to heroku, but it might be possible to get the same result by just merging {branchname} to master without that step.
Of course, if you aren't using 'master', substitute the appropriate branch name in the relevant places above.