1) change ttl to 5 minutes
2) wait until previous ttl expires (you need pre-planinng for this)
3) change servers to new address
4) change dns entries and restore ttl to what it used to be
5) have a machine answer at the old address that points people to the new machines
That's how we used to do these. :-)