That's the thing: They are not placing anything on your phone. They insert the tracking IDs into your traffic as it passes through their network. There is nothing you can do about it except encrypting your traffic (using a VPN or forcing HTTPS everywhere).
I don't see how encryption (VPN or otherwise) can have any effect on this. You send an encrypted request via web and they inject a tracking ID on top of your encrypted request. If the website you visit has any trackers or beacons looking out for that tracking ID your visit is immediately identified and shared with Verizon/AT&T's network, so they can effectively track any site you've visited that has an affiliated tracker/beacon.
----------
Sure there is. Get an AdTrap for your home network. You can even set up a proxy so that all your away traffic is routed through home. It gives you a bit of performance hit, but ad-free browsing and content streaming is fantastic.
That will block the ads from reaching you but it will do nothing to prevent them from tracking everywhere you go, which I think is by far the bigger threat. You can already avoid most ads using browser plugins like AdBlock. That's irrelevant.
----------
Meh.. if I have to see advertisements, it might as well be about stuff I'm interested in.
Right, because advertisers will only show you ads you want to see, as opposed to using your web browsing habits to fine tune which UNWANTED ads to show you.
I don't remember the last time I was shown an ad for something I would consider relevant to my wants and tastes. If that's how advertising really worked we wouldn't hate ads so much.
----------
An anonymizing VPN like Viking or an equivalent will circumvent this. They cannot embed a cookie into an encrypted stream to your VPN server which is marshaling all traffic to and fro.
Once again, this has nothing to do with cookies and VPN is useless against it.