Magazines and newspapers may not track you to the extent that websites can and do. But they certainly sell your information to third parties. And they have at least some basic profile information about you (if you're subscribing to Cat Fancier, it's a pretty good bet you love cats). Even an address or zip code provides a likely income range, political leaning, etc.
Billboards.... well that depends what you consider a "billboard" and what you consider "tracking". There has certainly been stories here on HN about eyesight tracking, stores tracking you using cell-phone beacons to see where you are going. These things can and have been used in signage (i.e. "small billboards").
But that's not really the point, anyway. My original point was that it was not "backwards" to pay for a particular service and have it show you ads. It's very, very common. And in most cases it's actually the norm, in almost any type of media. So I stand by my original point: showing ads is not "backwards", it's the norm.
The other things you mention - magazines, newspapers, and billboards - usually don't track you and build a profile on you so they are less objectionable.