Thinking this through a couple of options come to mind.
(1) Get a 4G router as opposed to a dongle, assuming your Firebrick has an available Ethernet interface. There are routers around that can be put into bridge mode, and in that mode they offer the WAN IP address via DHCP to the router. That way your Firebrick has direct control of the external IP.
(2) Stick with the dongle. NAT and everything, but use AA L2TP from the Firebrick to get a proper routable IP address, and IPv6. Then you can choose any 4G service based on price, service availability etc.