I tend to believe that authentication details belong in the header, not the URI. If you rely on a token being placed on the URI, then every URI in your application will need to be encoded to include the token. It would also negatively impact caching. Resources with a token that is constantly changing will no longer be able to be cached. Resource related information belongs in the URI, not application related data such as credentials.
It seems you must be targeting web browsers as a client? If so you could investigate using HTTP Digest access authentication or issuing clients their own SSL certificates to uniquely identify and authenticate them. Also, I don’t think that session cookies are necessarily a bad thing. Especially when having to deal with a browser. As long as you isolate the cookie handling code and make the rest of the application not rely on it you would be fine. The key is only store the user’s identity in the session, nothing else. Do not abuse server side session state.
If you are targeting clients other than the browser then there are a number of approaches you can take. I’ve had luck with using Amazon’s S3 Authentication mechanism.
This is all very subjective of course. Purity and following REST to the letter can sometimes be impractical. As long as you minimize and isolate such behavior, the core of your application can still be RESTful. I highly recommend RESTful Web Services as a great source of REST information and approaches.