How to authenticate a user which exists in an external site?

Question

I would like to authenticate a user which exists in an external site.

Here is a use case:

1. In Drupal, user enters his username and password and hits submit.
2. Drupal tries to find that user in it's system and does not find him. At this point an error message is still premature.
3. Drupal then runs a custom function which does a REST call to an external site. The REST call validates the username and password.
4. If the username and password pair is valid, the REST call returns a success code.
5. I then log him in.

Is this possible? If so, how? What hooks do I need to implement? What method should I call to log a person in?

I can programmatically log a user in via

$form_state['uid'] = <user_id>;
user_login_submit(array(), $form_state);

but user_id needs to exists in Drupal for this piece of code to work.

I am using Drupal 7.

Thanks.