This requires a NAT box with ...

Not quite, all it requires is a routing firewall (it's possible to do even with a bridging firewall, but that requires dirty MAC-spoofing tricks).