Cross-domain user tracking without 3rd party cooki

How are cross-domain web tracking services implemented (e.g., for behavioral advertising), now that the majority of people are browsing with 3rd party cookies disabled?

More explicitly, how does a third party tracking service recognize that two requests to different domains are coming from the same person?

Some options come to my mind:

Maybe iframe-based, by embedding a tracking page from the third-party tracking service into various sites. This included tracking page should be able to set first party cookies for the tracking domain (?). If the included page is unique for each tracked page, it should be possible to match the request to the website the iframe is embedded into?!
IP + user agent based (unreliable)
browser fingerprinting and clock skew measurements (I hope this is not already in common use today)
Cookie handover, that is, append the session ID as a paremeter to all links between the various pages. The visited page can then set its own cookie with the same ID as the referring page. Problem is, this does not work if the second page is not visited by clicking one one of those prepared links.
Using non-traditional cookies, such as Flash Cookies. Maybe some of these monsters don't honor the same-origin policy?

So, how is it being done?

EDIT: I just noticed that disabling 3rd party cookies will only prevent the creation of new cookies, but existing ones are still readily sent to the third party domain. Hence, one could somehow redirect the user to the 3rd party tracking service, which sets a first-party cookie, which could then later be read by a web bug. Interesting.

It depends on the service but for behavioral advertising it's still mainly being done using third party cookies. Most people currently don't block them so it works well enough to be useful. They are enabled by default in the major browsers and not many people mess around with the settings. The last time I saw a statistic on it the number was less than 5% but this can vary considerably depending on the demographics of the users you're looking at. In the work I do I generally see much lower numbers of cookie rejection rates.

Tracking is an inexact science anyway as there are multiple things that can disrupt the linking of people to web visits (such as the common trend of people using multiple devices and browsers).

My personal opinion on the subject that I think you're getting at is that the Online Advertising Industry needs to be careful about what they do in this area because public opinion on the subject appears to be confused and could lead to a rejection of more than is necessary for privacy reasons.