To be successful, in a fast moving startup we must move away from maintenance windows, and scheduled downtime. The team I am currently working with has been beaten into submission, and now deploys multiple times a day. This has allowed us the peace of mind to fix, iterate, change, and break production all in minutes. The idea of continuous deployment is not a new thing, nor a fully conquered problem.
You must decouple your services from your database, you must have lots of tests, and you must code review like a boss.