Rolling upgrades of packages

This is a use case Clint asked me to file.

Say I have a 4-node mysql slave cluster (all readonly for query load balancing); I need to deploy a new mysql package to all of them to fix a security bug, but I don't want to re-replicate 100's of GB of data back onto them.

Being able to tell the consumers of the interface that there are only 3 nodes, run apt-get upgrade on the 4th node, then tell the consumers that the upgraded node is back, and that one of the others is gone, rinse and repeat, would be pretty awesome.