Verizon operates at the network layer - if you are on their network presumably they will copy the real value over your garbage value.
If you aren't on their network then they can check IP address and ignore values not from the Verizon subnets.
There are a couple of other solutions you haven't mentions:
VPNs: Annoying and currently too hard for most people. Perhaps it is time for device (PC and mobile) manufactures to consider offering VPNs integrated with their devices.
Competition: If the US had a more competitive broadband market then people could choose other providers.
Legal action: If Verizon was sued and lost over this then it could have a cautionary effect. However, the loss would have to be huge for it to have an impact, and large financial settlements generally require proof of significant harm. That's going to be hard in this case.