Here is the EFF page on how to track browsers without using cookies:
Naturally you can reverse engineer that code from the frontend side.
Another option is to store the unique identifier in an image, e.g. the store logo. Or the browser history URLs can be looked at, as per those sites that know if you have been to 'example.com'.
Naturally your detection code can be obfuscated by putting it through the closure compiler.
These 'cheats' do need scripting, but only Windows Server admins have that turned off, don't they? Nonetheless, some plan B will be needed...
You can geoip your site visitor so that you only need worry about the cookie problem if their IP is in one of the EU countries.
Only if you cannot automagically identify your EU visitor would you then need to degrade gracefully to cookies - and asking for them. Naturally you'll be wanting to do that with a huge un-bypass-able modal dialog-box showing the Cookie Monster hugging Peadobear asking how you wish to be stalked today obviously to the tune of your favourite Rick Astley song - that should help with conversions...
Yep, this new cookie law is silly, but cookies were never intended to track people in the first place, were they..?