Uhm, sure. Just slowly decrease the TTL on your name server until you are ready to renumber (and the TTL is set to something ridiculously low such as 1 minute). The customers will then experience something like a 1 minute outage when you renumber. If we are going to start getting into the procedures of HOW to renumber this should likely move to the PIER mailing list. I think if in general people become more interested in HOW to gracefully renumber themselves and their customers instead of worrying about how hard it is to do they would see that while it is work, it isn't really all that hard.
Why don't you slowly decrease the TTL on your name server until you're ready to renumber. Configure your web server bind to the old address(es) and new address(es). Re-number in the DNS, and your customers will experience something like no down time. Then put the TTL back to where it normally is. -Christopher