I have developed many stateless RESTful webservices for a mobile application in Java and they are working very well.
For example:
You do not need 2 log in procedures. Just use the Facebook SDK!!
i) In your app would be a login with facebook button.
ii) User clicks on it and is then redirected to the facebook login page, where the user enters his credentials and facebook returns a token to you. You do not have to worry about the user's facebook credentials or storing them anywhere! Facebook will handle that for you. Consider the FB login part as black box to your app - you simply make a FB SDK's login call and it will do some processes and give back a access token to your app.
iii) Now, you can exchange the access token for the user's profile information. Enter this profile info to your database - that will ensure authenticated call.
Once you have verified that the user is logged on you can do whatever you want.