I swapped my new router in this afternoon, and was ultimately able to get the previously described configuration working. In case anyone else reading this finds it interesting/useful, here's what I needed to do to make it happen:
Preconfigure the new router - This can all be done without interrupting the original network at all: Setup one interface on the existing LAN and connect it. Setup one interface as WAN. Setup a third interface OPT1 (or whatever you want to call it), give it a static IP in a new, separate network.
In the new router, configure a firewall rule for OPT1 interface to allow all traffic for all protocols. Without this, the new router's firewall will block all traffic coming from the old router.
Swap the cables: Move the cable providing your internet over to the new router's WAN port. Then with another cable, connect the WAN port of the old router to the OPT1 port of the new router.
Set IP configuration of the WAN interface to be part of the network that OPT1 is configured for.
That's it - the network will now work and function like in the diagram above. Hosts will have connectivity, whether they are using the original configuration, or have been updated to use the new router as the default gateway.
Note: There are many things this will break that aren't detailed here - VPN's/Web Caching/IDS/etc. The configurations in your old router need to be moved to the new one before they'll do anything, so if you have any mission-critical stuff going on in your router, plan accordingly.