I'm sure someone is probably working on this, but what about a service that generates a one off seed for the second stage of auth, married with either a desktop or smartphone app for generating it for the user. Lose your phone/laptop/PC simply cancel it remotely so it stops generating, same as you would if you lost your bank card.

I'm sure I'm missing something, but I'm not sure what.

EDIT: I'll let the post stand but I need to read more clearly, I thought Google Authenticator was purely for Google services.