I haven't tried this, but this module sounds like it does what you want:
http://drupalmodules.com/module/openid-autoregistration
"Module allows automatic registration of (successfully logged in) OpenID users, even in case OpenID provider didn't supply data necessary for Drupal user registration (valid username and email)".
Ilmari
2010-04-11 11:55:23