When using a master plus multiple slaves, how do I change over from one server to a brand new one with minimal downtime?
I don't know how well this works on Heroku but I think it should work if one is using streaming replication internally.  I would recommend repmgr which is an open source replication cluster management tool from 2ndQuadrant.  This provides a general monitoring and management framework for replicated database clusters.  In 9.3, repmgr will be less necessary but still may be helpful for integration into heartbeat systems.  It provides a command line tool for failovers, preparing slaves, etc.

If you have to do something like this manually and repmgr wont work for you, basically, what you need to do is this:


turn off the master (shoot the other node in the head)
promote the slave to a master
re-base your other slaves and point them at the new master
turn your old master into a new slave when you can bring it up.


How you do this will depend to some extent on the replication approach.