How to authenticate a user which exists in an external site?
Based off of your comments, it sounds like you have the basic procedure down: hook_form_alter the user_login form, and use your own validation.

If you take a look at user_login_default_validators, I think your problem is that you need to swap out user_login_authenticate_validate with your own, but still get the form back into the same state.

I think your best bet is to do your RESTful authentication in a validator, and then set $form_state['uid'] to a valid user in the system.

My suggestion is to create a single user that you map all of your REST logins to, and use this as $form_state['uid'].  This way, you still can use the permission system across your site.  To get them logged in, you can just do a user_load with the $uid of your special user.

I am not positive, though, if having all of these users will cause any problems with sessions.  I have only done something similar with Drupal 6 and each remote user got their own account in Drupal.