The "cookie" part is irrelevant. With Verizon injecting data into the stream, your id can be read by the site without cookies. Collusion between entities will build a profile of the user. The only way to stop it is to use an encrypted connection. Tor isn't a great daily driver, so that leaves vpns. 
The troubling part, is it probably won't stop with Verizon. You can leave them, but most probably won't. It'll end up being another expense and hassle for the people that care. The rest will be silently screwed.