Micropayments
The solution to ads seems very simple to me, so I'm surprised this hasn't been done.
You (end user) create an account with ad provider, and pre-pay something like £10 (or $10). Ad provider places cookie on your PC (they're good at that!).
When you visit a site that uses said provider, it sees cookie and bills you a small amount (say 0.1p) out of the pre-payment, which goes (after commission) to the site owner. Then, instead of serving you an advert it serves you an empty box of the same size (so as not to screw up the content), or more likely a box saying "You have just donated to this site, thank you!".
As part of the contract with the ad provider, no tracking info is supplied to the site owner. They do, however, receive an income towards hosting and operating the site.
If you don't sign up, or you do but your account balance drops to zero, you get adverts as usual.
Easy to implement (site owners do nothing, they just display ads as normal, except some users won't see them but the site will still earn revenue).
What's wrong with this model? (Or should I have patented it?)
Biting the hand that feeds IT
