Joseph Scott has a recent post to his site looking at the idea of stateless CSRF tokens and how to create them while avoiding the typical "store them in a session" mentality.
This is all fine and good until you want to avoid using PHP sessions. Perhaps you have several web servers and don't want to deal with shared session storage. Or have servers in multiple data centers and don't want to try and sync state across them. What ever the reason, popping a token into $_SESSION isn't an option in this case. In short you want some sort of stateless CSRF token.
He looks at two methods to help get around this issue. The first method is based on known values that won't change very frequently (say, maybe 24 hours). His second method, however, has a bit more strength to it. His idea uses a combination of a key, the current time, a timeout and a known string of data - all base64 encoded.