Your assumption is that a phone must present a permanent identifier to the network on the physical layer but I don't think that is true. You could have temporary identifiers instead. If you have multiple concurrent ones and stagger their renewals, and proxy all traffic over tor then it seems like goal would be accomplished.