Another trick we use when we move A, CNAME, SOA or PTR records is to change the TTL of the entry of interest to 1. This way, when the default TTL expires, and hence all cached information becomes stale, the DNS servers around the world will require a new, "fresh" answer. This time the answer will have a TTL of 1 (on second), which means that the specific entry (or whole zone file if you like) will not be practically cached anywhere. Hence, once you change an entry, it will be available immediately to anyone, so there will be zero delay/"downtime". This can be achieved also with the zone regarding the SOA records you wish to change. This way, nobody will cache your "old" DNS servers after the TTL of your zone file has expired, and each change will become public immediately.
Good luck.