This was brought up in the first autonomous crash death thread, I responded to SVreX about what would be required to make an untrackable cell phone - basically it's not possible on the phone end, it's up to the telco to restrict access to, and not-record your cell phone's location. Your phone's transmissions could still be triangulated by spooks with radios, but there wouldn't be a convenient detailed log of where you've been ready to pull up from the telecom's network on request as there is today.
Then I thought, there are already ways to own an untrackable cell phone, for certain values of "cell phone."
Cellular networks need to know where the phone is physically in order to work, to make a long story short. It's trivial to store and share that information, and thus the privacy nightmare is born. If you can make calls without using a cellular network on the other hand, you can avoid this problem. The solution is VoIP and Wifi (ideally with a plan for a public wifi service, if you want half-decent coverage).
If you get a SIP account at your VoIP provider and connect it to a client on your cell phone, you can send and receive calls and the VoIP provider, if they wish, could only log the IP address you've logged in from. This could be traced to a rough physical location with a lot of work however.
So the next step in improving privacy would be to tunnel the VoIP traffic through a VPN service. This way the VoIP provider will only see the IP address of the VPN provider. Your VPN provider will have access to the same IP address information you're now hiding from your VoIP provider, but there are VPN services available from eastern-European providers who promise to never log your IP information.
If that's not good enough, you can move up to the next step, which is somewhat theoretical - running your VoIP traffic through a darknet instead of a VPN. Performance-wise it might not work well, most darknets are slow and laggy due to the nature of how they work - the only "fast" one I'm aware of is I2P and it's not (yet) capable of passing VoIP traffic through outproxies. If it performs well enough, the IP address visible to the VoIP provider would be constantly changing and never trace to your physical location (unless the exit point happens to be near you by chance ). If your VoIP traffic is encrypted, even the NSA could have a bloody hard time finding you.
Of course all of this work could be undone if you allow tracking through other methods, such as by installing any app on your phone that tracks your location (which is probably a majority of commercial apps, not counting those included with your phone that have location-tracking capability). Also you'd be likely to lose connectivity fairly often if you're out of range of wifi - in other words, if you're not a city-dweller. But it is possible. I actually have a plain VoIP connection from my personal cell phone to my office VoIP server - using this, I could make calls without a cellular connection.