It sounds like you're making rolling updates across your app server cluster, version n -> n + 1. You have to separate database updates into innocuous and harmful, and your developers have to signal that state for deploy.
Changes:
a) Schema changes and row updates that are compatible with 'n'. No downtime, no worries.
b) Schema changes and row updates that are _in_compatible with 'n'. Ideally this requires downtime, but I've seen architectures that get away with live rolls by grouping app server updates by shard.
c) Database changes that will have a severe performance impact, e.g. index/update a massive table or hit some other perf corner of your db. Downtime or you invest in a key-value or FriendFeed-style architecture.
Changes:
a) Schema changes and row updates that are compatible with 'n'. No downtime, no worries.
b) Schema changes and row updates that are _in_compatible with 'n'. Ideally this requires downtime, but I've seen architectures that get away with live rolls by grouping app server updates by shard.
c) Database changes that will have a severe performance impact, e.g. index/update a massive table or hit some other perf corner of your db. Downtime or you invest in a key-value or FriendFeed-style architecture.
Most agile updates tend to be (a), luckily.