Off the top of my head: when rasterizing text, use a pseudo-random, invisible perturbation of a few pixels in the output bitmap seeded with a hash of the current domain and perhaps the number of days since the epoch.
If third-party scripts are used to perpetrate these ever-cookie exploits, then the NoScript extension in Firefox may be effective against them. With NoScript, you can block Javascript on a site-by-site basis. Many websites are quite functional even when you disable much of the third-party Javascript that they rely on (Javascript fetched from domains other than the one matching that site). For instance, I've never had a problem with any site that uses Javascript from Google Analytics, even though I block it.
They've gone and labelled the many different ways a browser can be tracked across websites as "ever-cookies". Most, if not all of the methods mentioned have been used for more than 12 months. That's a long time in the online advertising world.
I would think you could get away with using (ip, user-agent) to, fairly reliably, recreate a cookie. It seems like it would be pretty rare for a user to clear their cookies _and_ get a new IP address at the same time.
Bingo: the beauty of the cookie is that the client stores it for you.
If you start storing IP address and user agent info, you open yourself to attacks that try to flood your database. If a botnet visits your website with millions of different IP addresses, and each one fakes half a dozen user agents, oops!
(The lesson from TCP and why it has SYN cookies now.)
Off the top of my head: when rasterizing text, use a pseudo-random, invisible perturbation of a few pixels in the output bitmap seeded with a hash of the current domain and perhaps the number of days since the epoch.