But they did! Many times over!
The current solution isn't the only way to deliver ads to the right audience - it's just the cheapest one. It outcompetes all other approaches. The solution is thus simple: just ban it. Everyone will then go back to whatever is the next cheapest option. Rinse, repeat, until the cheapest option is one that doesn't compromise privacy and isn't destructive to the communications medium.
So what are the different, older ways of delivering well-targeted sponsored content? For starters, opt-in approaches. Mail catalogues, e-mail catalogues, yellow pages, catalog websites, trade shows, etc. - all kinds of services where it's the user who seeks out advertisements. People want to spend money on things, want to find solutions to their problems, want to save money by finding cheaper alternatives. You don't have to shout at them to get them on the market.
> the biggest loser of non-trackable Internet would be small businesses and startups that are trying to find their audiences
I'm somewhat skeptical about this, but even if, I also think that the amount of advertising deployed is keeping the market in an artificially oversaturated state. There's more companies selling commodity products, competing on advertising alone, surviving only because they manage to trick people into buying things. Without so much unsolicited advertising, some of those would have to fold, but I think this would be extremely good for everyone - less spam, less resources wasted on unnecessary production, and less resources wasted on the zero-sum game that is advertising in a highly competitive market segment.