How do I update DNS without causing an outage?

If we KNOW we will be moving an IP address, we turn down the TTLs for that record. That tells the DNS servers on the internet how long to keep that IP in cache. When we move it over, the rest of the 'net catches up fairly quickly. Once the move is done, we move the TTL's back to their normal value.

We did this a couple weeks back when we needed to change our MX record. It uses the same steps as an IP change. First, we lowered the TTLs for the MX records from 1 day to 5 minutes. We then waited 2 days for the change to propagate. We updated the MX records on our DNS servers, and within 10 minutes every client on our network was using the new data. Looking at mail logs, it took about 2-3 hours for the rest of the internet to catch up. Once the change was made, we then raised the TTLs back to their previous default.

Probably the easiest way would be to add the new IP as a secondary IP on the box, then update the DNS record. After a week or so you should be safe to remove the old ip and make the secondary ip the primary address.

If you're just renumbering existing hardware, you can do as Zypher says and dual-address over the transition period. If you're actually moving the services, though (say to a different hosting provider) you can use dual-NAT to redirect traffic to the old address to the new one. This does pre-suppose either full control of the old hardware or a helpful hosting provider, and it messes with your IP access control/logging (all redirected connections will appear to come from the old address), but it's worked quite successfully for me several times when I've had to transition services between networks.