Demote one of the servers with DCPROMO.
Promote it with DCPROMO again, creating a new forest and domain.
You should be able to backup your GPOs and restore them from backup in the new domain. The exact procedure may differ slightly depending on your version of Windows.
Consider using DNS conditional forwarders or something to allow name resolution between the two forests. There is more than one way to accomplish this.
Create a trust between the two domains, if company policies allow it. These will allow authentication between the two new forests.
They can be on the same network. You don't have to mess with your network/router if you don't want to.
edit: Here's some info that might help you in migrating your GPOs: http://technet.microsoft.com/en-us/library/cc781458%28WS.10%29.aspx