Now that I had time to work on this after hours when traffic is to a minimal, here is my solution. It only took 5 minutes to config and test. All seems fine.
1. Setup WAN Interface with the new public IP
2. Created a ProxyARP VIP for Old Wan IP
3. FW Rules don't need changing … nor do I need 1:1 mapping
4. Downloaded current XML backup file
5. Copy/pasted all my NAT rules in backup file for quick duplication
6. Added this to each duplicate rule: <external-address>Old IP</external-address>
7. Restored FW with updated XML file
8. Tested a few of our services and sites which still have DNS with Old IP... all OK
9. After the Old IP expires I just delete the VIP and duplicate NAT rules.
I hope this helps someone with a similiar issue.