Advertising on old style TV, newspapers, billboards did not impact on privacy. Even non targeted advertising on the web can impact privacy because our browsers send requests to the ad servers and that's the beginning of fingerprinting, even with Javascript disabled.
The only way it would work on the web while fully preserving privacy would be if (1) ads were stored on the server of the website you're accessing or proxied by it, and (2) the website owner would never give the ad provider server logs. It can be done (and used to be).
When i first got into web hosting in the early noughties this is how i remember it being done. Want to advertise my game server on some site? Provide an image url and a link url. That was it.