I've been doing a little bit of research into ways to misuse browser history and cache and came across a very simple technique for tracking users without the need for cookies. Firstly, a demo. If you watch the HTTP requests you'll see that there are no cookies being used.
To track a user I make use of three URLs: the container, which can be any website; a shim file, which contains a unique code; and a tracking page, which stores (and in this case displays) requests. The trick lies in making the browser cache the shim file indefinitely. When the file is requested for the first - and only - time a unique identifier is embedded in the page. The shim embeds the tracking page, passing it the unique ID every time it is loaded. See the source code (thanks to Nathan for pointing out the date error).
As to how useful this actually is; the only use cases I can really think of are not exactly legitimate. The most obvious is to track users who won't accept cookies. This does have advantages over cookies too; namely that this kind of tracking is completely silent. Virus scanners which search for an delete tracking cookies won't affect sites using this method. Likewise, manually clearing cookies won't work.
The most practical implementation would be to use this in concert with cookies to make tracking IDs more sticky, so they could outlast a user clearing their cookies. I've also been looking into adapting the link colour hack to store custom values in the browser history (this is easily doable). Combining these three techniques would mean a user would have to simultaneously clear their cache, their history and their cookies to circumvent tracking.