1) for each new session, generate a secure random token as a property of the session
2) serialize session properties to a byte array and encrypt the array, using, say, AES.
3) set the encrypted session state as the value of the (HttpOnly) session cookie
4) when rendering secure pages, decrypt and include the clear CSRF token in the X-XSRF-TOKEN HTTP header (only top-level HTML pages, no other requests)
5) on the client, include the CSRF parameter in your XHR requests and form posts.
6) on the server, verify the CSRF parameter against the value in the encrypted session state from the session cookie
The only shared server state in this case would be the secret key used for AES; this could be part of the production environment configuration and updated with each deployment.