We do seem to have to worse of all worlds at the moment. It is very difficult for users to exercise control over good sites, and it is practiaclly impossible to control bad sites.
I wonder if a solution would be to tie third party cookies to the parent page. So that by default a Facebook cookie on a Guardian page could only be retrieved when the user is on the Guardian website. You could then have options within ther browser to explicitly allow cross domain cookies if the user wants (and send the actual Facebook domain cookie).
There is no reason limiting adservers from doing what you describe using first party cookies: they all make use of Javascript, so it is trivial to just set a first-party cookie.
We actually took that approach to be compliant with the EU's cookie law; if a visitor rejected third party cookies, we fell back to first party cookies.
I wonder if a solution would be to tie third party cookies to the parent page. So that by default a Facebook cookie on a Guardian page could only be retrieved when the user is on the Guardian website. You could then have options within ther browser to explicitly allow cross domain cookies if the user wants (and send the actual Facebook domain cookie).