Due to some changes in tower frequencies, I ended up having to carry two phones with me. It hasn't been that bad actually and maybe the idea can be expanded further. There are then two phones, a Burner Phone that has a phone line, internet access and nothing much. This phone is untrusted and runs the usual bloatware from the carriers, etc. The second phone, let's call it 'Good Phone', tethers to the Burner Phone and runs VoIP, apps, contains contacts, browser logged into services, etc.
As it is, this solution has a number of problems that could be addressed if this is used by others: the wifi tethering should be disabled while being at home/work (that will need to use GPS because the wifi antenna is already being used by the tethering). And some way to dynamically ship contacts from one phone to the other will be good (otherwise the phone number needs to be typed in every time, that's not that bad, nobody calls on the phone anymore).
There are projects that run an isolated, secure environment within one phone. They seem to address a different threat model (malicious software in the phone attacking the app in the secure environment). The thread model here is privacy, the Good Phone has no phone number associated with it. (It could be also a very small tablet, like what N810 was back in the day.)