DNS standards specify a minium TTL of one hour, but I've seen TTLs as low as 5 seconds work without issue. Set the TTL on all zones & records to something really low, then turn up the new server with a copy of all your zone info. Make the DNS server switch (either by chaning out IP addresses or through your registrar) and your downtime should not exceed your TTL (which should be as low as possible).
DNS is a squirrely beast, but most sysadmins get to know it well - post here if you have any questions.