There's no reason a new device on a mobile network should be given it's own IPv4 address.
On the 3G mobile network I use (outside the US), each device gets a 10.10... private IP. Traffic then goes through several hops of the private network before coming out into the internet with just a handful of public IPs for the many thousands of customers.
This causes it's own problems (for example, breaks OpenDNS or anything that assumes one user = one IP) but doesn't waste IPv4 addresses. No reason why the US mobile networks, and even regular ISP's, can't do the same.