There are also options like Erlang and Node.js where hot code-swapping is possible. Although having a second database is useful as a slave, of course, I don't think it is necessary to run two copies of the database just to redeploy.
Github just redeploys by killing and restarting Unicorn workers gradually. It's graceful, because any worker that is handling a connection won't be killed, so you won't get any dropped connections. http://github.com/blog/517-unicorn
I'm not hugely concerned about swapping out application logic, since with a bunch of application servers it's possible to pull some out of the pool, upgrade them, then use the HTTP load balancer to redirect all traffic to the servers running the updated code.
The big challenge is making changes to the database schema and co-ordinating the deployment of those changes with the switch over of traffic to the new application logic.
This may not be a perfectly generalized solution, but is it possible to structure your system such that when upgrading from version i to version i+1, version i of your app is compatible with both versions i and i+1 of your database and vice versa?
Say, for example, your factoring a column into it's own table. Don't just drop the column, set up a trigger to synchronize the original column value with a value from one of the rows in your new table.
You could then finally drop the column in version i+2.
I seem to remember finding a book on database refactorings that covered this technique in more detail. It was online so you could try Googling for it.
Github just redeploys by killing and restarting Unicorn workers gradually. It's graceful, because any worker that is handling a connection won't be killed, so you won't get any dropped connections. http://github.com/blog/517-unicorn