As for consent, you have to be able to refuse. A consent box popping up each time would be the dumbest way to do this, but not that different than those full-screen email/newsletter begging boxes we have now.
If we agreed that even incognito browsing contains the traces of PII, publisher has to get my consent, explicitly, that's the whole point of GDPR. I see no other option than to do popup window for each new visitor (where new == has no associated cookie). What are other options?
Well, it's 2018, and most publishers rely on some 3rd party ad-tech to serve the ads. They don't have direct contracts with advertisers, and definitely has no tech in house. If 3rd party calls are prohibited, their ad revenue disappears overnight.
Will be interesting to see how it develops.
So if your interpretation is correct, and GDPR affects even completely anonymous users, I'll be seeing and clicking "consent box" each time I go read a newspaper or just do general browsing. Like the "we use cookies" stuff, but on steroids.
EDIT: but still, I find this hard to believe, tbh. It means no ads served to anonymous users, and this has consequences I can't even imagine.