Note to web services businesses: give your users the option to have a local account, and give them an option to change from one 3rd party authenticator to another or to a local account.
This would be an ideal solution for this situation, but the problem remains: if I cannot authenticate via the 3rd party initially, the service has no way of knowing that I am actually the owner of the account. I am not sure what the working implementation of this looks like.
Email verification with a newly generated local password. That's what Meetup did after I quit Facebook, and it was only 3-4 minutes of friction.
Doh. Of course - that would have been easy and effective.