Glad to hear you got the address translation problems worked out.

Yes you can do what you mention above but you will need to set up static nat translations (either 1 to 1 or forward any traffic on a given port to a specific internal address) for any servers that need to be accessed from the internet. And your dns entries need to be changed on your external facing dns server - especially important will be your mx record and any web server addresses.

It really wouldn't matter if you were using rfc 1918 addresses or the ones you are using now. Nat needs to be set up so that internal users are all natted to a single or group of addresses on there way out and your servers/services that are internet accessible are translated on the way in.

The best way you can do this is by actually setting up the spare firewall and to do it in a "simulated" environment first.

First draw it up on a board, every computer that has a connection through the units and all of the clouds.

Check that you do not have locked ip's ie they are locked into the software somewhere fx for licensing or hardcoded into some software.

Take your spare (if you do not have a spare firewall then this is the time to get one) and configure it as it should be.

Test the config with a couple of portable computers so that all the tunnels through the firewall is correct and all the nat, static and routing is correct.

Then write a idiotproof scheme to the server operators stating what ip the server has today and what ip they should change it into.

Then you do a point by point scheme over everything that should be done in order to do the switchover, here you put fx change the dns addressing scheme and such.

This is also a nice opportunity to set power cabeling and such things correct if they are not.