Persistence across services

but we cannot use Cookie hash because the server does not use cookies

Do you mean the client (requester) doesn't support cookies? Cookie persistence doesn't rely on the back end servers supporting cookies, on the client (normally a browser).

The trick is providing some form of information that the client will relay, and that is unique. HTTP is stateless, so you don't have many options other than cookies (the easiest method), source address (if you don't have to worry about NATs), and perhaps something in the payload that is persistent and unique (ie. a sessionid that's always in the request). If you cannot support any of those methods, then it will be VERY difficult to do any kind of persistence.