The "old way" is actually to install a new CA on the device. Then the proxy can just dynamically create dummy certificates signed by that CA.

This is simple on the client and avoids any security warnings. It's supported in quite a few firewalls and even squid, so it would be very easy for a carrier to roll out tomorrow if they needed to.