Eu já lidei com isso no passado criando um sub-domínio www2.whatever.com, que o novo servidor escutará em além para www. A chave é que não pode ser um redirecionamento para www (caso contrário você estará de volta à estaca zero).
Depois de alterar o DNS para apontar www no novo servidor, você altera o servidor antigo para redirecionar 302 www para www2.
O resultado é que os clientes que obtêm a entrada DNS atualizada funcionam como esperado, enquanto os que recebem uma entrada em cache obtêm um redirecionamento temporário para www2 (que é novo e sempre apontado para o novo servidor). Eventualmente, seu cache expira e suas tentativas de se conectar a www apontam para o novo servidor.
Após um tempo suficiente, você pode redirecionar o www2 para www, mas acho que na maioria dos casos seria bom excluí-lo.
Alternativamente
Você pode ter todas as suas solicitações através de um proxy. Eu uso o plano gratuito do CloudFlare em todos os meus sites, e como todos os pedidos realmente passam por eles, mudar o endereço IP dos meus sites é realmente apenas altera uma entrada no seu proxy. Os usuários finais veem os mesmos endereços IP no DNS, então a mudança é basicamente instantânea.