There's also the psychological aspect. People are used to advertising in every other form of media, so seeing it online is acceptable. People expect online services to be "free", and few really understand the business transaction they're a part of, or the repercussions of it. Even when they do, many are willing to make that transaction because they value the service more than what they're giving up to access it, and they have no other choice.
So it ultimately boils down to offering the choice to pay with currency, and making it frictionless for both consumers and publishers to use. And educating consumers about the real cost of advertising.
The unfortunate reality is that advertising has become so profitable that in order for the payment system to work, companies would have to price their services higher than any consumer would be willing to pay for them. Or they would have to settle for lower profits, which no company would actually do. This is why you see that even when a service has a payment option, they still inevitably choose to _also_ show ads. Advertising money is simply irresistible to most people, and few have the moral backbone to resist it.
Paying for my own ads felt similar to shopping at a local bookstore: I paid extra for the culture I wanted to see. There's a market for it, but, you're right, it probably wasn't big enough to justify its existence at Google.
Does Google need a reason to shutter something?
</GoogleRant>