I've thought about this a bit. Consider a consortium of like-minded privacy-concerned people that has a pool of virtual SIM cards (exceeding the user base by perhaps 2x or more). The group pays for the whole pool of SIM cards (end users pay the group, perhaps through bitcoin). Participating phones check out random virtual SIM cards (using some kind of cryptographic signature perhaps similar to blockchains to assure anonymity) periodically in order to ensure apparently random distribution. All transactions flow over a VPN to a common network and the phone itself is disabled (use VoIP). Web access runs through Privoxy or similar filtering to ensure there are no traceable bits. This should be fine until you start installing other apps.
This probably requires special hardware in order to "spoof" the consortium's SIM cards and swap between them with minimal downtime.