As far as database migrations are concerned, GitHub (and others, of course) takes the perspective of migrating before the code that uses those migrations go out. In other words, as @herge says in a sibling comment, the code that gets pushed needs to support two branches of code and two branches of data simultaneously. It's certainly some extra work (and can be pretty gnarly depending on the scope of the migration), but once you get to a certain point it's kind of the only way to do no-downtime migrations.
There's many possibilities to help with the actual migration process, depending on what database you're using. With MySQL, for example, you can do something like the process in lhm: https://github.com/soundcloud/lhm
Zero-downtime deploys aren't super difficult in Rubyland anymore (many have written how they achieve it in Unicorn, for example), although I'm not as familiar with how other folk do it across other languages and platforms these days.