It seems to me that the best way to do this is to combine both approaches. There are some things you can do, but there's almost certainly going to be some clever way that people manage to circumvent these rules. One thing to consider is that the biggest threat is from the "omnipresent" companies like Google, Facebook, Twitter, etc, because they're the ones who have a 3rd party presence nearly
everywhere on the web. Tracking someone's
entire web history is a lot different than tracking 1 out of every 100 websites they go to, and the "big players" are the ones who are most likely to actually be scrutinized. I'm usually quite loathe to recommend any legislation, but I do think that these "big players" would likely comply with a legal requirement to respect "Do Not Track" requests, even if CoolBeanzTracker.biz would still ignore them.
In the end, I think the way forward should be to do our best to prevent our browsers from leaking such information, but also to punish people who, against our explicit wishes, take advantage of any small mistakes we make when we protect ourselves.
By analogy, it's probably not smart to go into a bad neighborhood at night alone with no protection, a large amount of cash and a flashy suit, but that doesn't mean that it's a silly thing to try and deter robberies and assaults on a societal level (either with social strategies like shaming and shunning or with violent strategies like law enforcement or retributive violence) - to the extent that it's cost-effective to do so.