Shameless plug: dotCloud (http://www.dotcloud.com) doesn't have downtime at deployment. It leaves your current version untouched until the new version is fully built, run, scaled and responsive. Only then is trafic switched over. If anything goes wrong on even a single node, the deployment is safely aborted. This is the case even for deployments which span dozens or hundreds of processes on several datacenters. It's a lot of work to get right.

(disclaimer: I work at dotCloud)