Perhaps this legislation gives you a clue about how on the ball some Govt's are when it comes to security matters?
What you are suggesting is a phone that changes its obvious identifiers, but the problem with that is some services may not work, maybe an app purchased from an app store, or the network services you get from your cell provider, like answer phone facilities when you are in a dead zone. So if your phone is acting like a character out of Scanner Darkly, just how will it operate? How will your friends know its you calling if they dont recognise your number?
To have a cellular network that allows random identifiers, you would need a system which accepts prepaid communication time, but in todays age, just like bitcoins is a public ledger how would you convince someone to build a cellular network that accepted untraceable communication time tokens?
Whether you like it or not, Science stole your privacy the day you were born and continues to steal your privacy including your thoughts. Perhaps your best bet for some privacy is to limit your contact with other entities whilst also trying to change the laws for the better but as this requires interaction with other entities, it seems like you want a paradoxical situation to exist.