It requires getting consent and sending the value of a query parameter that was appended to the ad link the user clicked (GCLID for Google, FBCLID for Meta, etc) with some random (but now pseudonymous, because Google/Facebook/etc can link the session ID to the click ID to a user account) session ID and then sending that same session ID when the user converts/does the thing you want.
If you get consent, you can also set a longer-lived cookie to determine if a user converts in a future visit.
> And even then, advertising without tracking worked just fine without internet.
There is even now a form of online advertising without any tracking (except in the most opt-in form of a discount code) which is sponsorships of videos, podcasts, articles, etc.
However, for search and display ads, which drives a huge amount of traffic to EU businesses, there's no effective way to run ads without conversion tracking. Obviously you can just throw money at Google/Facebook, but without conversion tracking, the average return on advertising spend will be 1-10% of what it would be otherwise and you will pay for a lot of junk traffic.
It's not unusual for B2C companies in the EU to make 80%+ of their online revenue from forms of ads that require conversion tracking, so it's impossible to expect businesses to refrain from online advertising unless all their competitors are required to also.
This all relies on getting consent as a lawful basis for processing, and is currently acceptable under the GDPR except that the major networks are all US companies who could be compelled to transfer the data to US authorities.
Even now, it is much more likely that a US CLOUD carve-out or other work-around for an adequacy decision with the US will be made than the CNIL interpretation will be followed to its logical conclusion, which is that EU businesses process personal data with any US-controlled vendor, even if it occurs in the EU.