On: Add two-factor authentication to your ssh in 30 se...

[count]

And how do you do that with cloud instances? :)

[pixelcort → count]

Some VPS providers offer "console" access to the machine, which would probably allow someone to drop down into single user mode.

http://www.linode.com/faq.cfm#do-you-provide-console-access

[Ralith → count]

Same way you do when you forget the root password on a normal configuration.

[justincormack → count]

Install a new instance! Its all disposable hardware.