It could use an ephemeral device ID and make its paging-channel connection back to its home network via a Tor-like mix network. I know that sounds like goofy sci-fi talk, but you can actually do this today with free software on Wi-Fi: run TCP-only Mumble over Tor to connect to your Mumble server, and periodically generate a new random MAC address (like Apple’s new phones do) and set up a new Tor circuit.

What’s left is how to pay for the Wi-Fi access anonymously, if people aren’t willing to share it with you for free. If your wireless network access is all done through a centralized company, like a cellphone carrier, you could easily use one of the Chaumian centralized-issuer digital cash schemes from the 1990s: the “bank” is your cellphone company, and they sign a “blinded” form of a bunch of “coins”, which you later sign over to wireless base stations in exchange for bandwidth. The protocol assures that the base station can confirm that the coin hasn’t been double-spent and that it’s properly signed by the bank, but the base station and bank together cannot figure out which coin it was.

Yeah, in 2000, after a car accident, I was surprised that the 911 dispatcher couldn't locate me using my cell phone.

I guess people are talking about 2 different things though, one discussion is about the implications of a radio (you and others are talking about this) and the other is about government capacity to gather the information revealed by using a cell phone.