Can the systems not communicate at all, or is it just that between hosting providers the normal Windows/AD ports are not open? If the latter, depending on exactly what is allowed it may be possible to set up a IPSec policy between them using a pre-shared key to allow secure full communication and promoting the new machine and then demoting the old after all services are moved. This would have the advantage of being a real-time sync throughout the migration.
Alternatively, moving a domain controller between sites could work (although will probably mean ntdsutil cleanup). Virtual machines can be useful for copying/splitting off a copy of a domain, although there are good reasons why Microsoft says to not use snapshots and it's best not to ignore that advice unless you completely understand the implications.