If part of a premium service was "no ads *and no tracking or scanning your stuff or your habits in any way*" (preferably with some way to prove it) I think I'd be more inclined to pay for it.
If clicking on a site had options:
- View free (ad and data mining supported)
- View for 2p (100% private and ad-free)
I'd pay the 2p. Assuming there's some way to prove that they're not lying, which yeah, wouldn't be easy. It'd need some interesting open-source "thing" to make it happen.