Session management : How to generate Authenticatio

I am trying to implement session management in my REST service. I came to know these guidelines while surfing :

Not using server side sessions - it violates the RESTful principle.
Using HTTP Basic authentication - Not possible right now, as I am asked not to use SSL/TLS (which is no doubt needed for Basic auth.)
Using Http digest - I heard this increases network traffic. This sounds costly, especially when my client is a mobile device.
Using cookies - I am told I should never rely on cookie for securing my important resources, they can be spoofed easily. Plus, I read about cross-site scripting attacks through cookies.
I am left with an option of generating authentication token ,which the user has to send everytime - which I admit is not "entirely" RESTful.

Now I need to know, how should I generate these unique authentication tokens, which are secure enough at a business level ? Is there some library for Jersey ? Should I go for OAuth..I have just read a little about them, are they useful in my case ? Please keep in mind that my target clients are mobile devices - can they access an OAuth service ??

For simplicity sake, I generate my own authentication token using UUID before encrypting the entire token with Jasypt:-

String key = UUID.randomUUID().toString().toUpperCase() +
        "|" + someImportantProjectToken +
        "|" + userName +
        "|" + creationDateTime;

StandardPBEStringEncryptor jasypt = new StandardPBEStringEncryptor();

...

// this is the authentication token user will send in order to use the web service
String authenticationToken = jasypt.encrypt(key);

The key contains the creationDateTime so that I can use it to verify the time-to-live. This way, if the user uses the same authentication token after X minutes, it will not work anymore, and I'll send back a 403 forbidden code.