A couple of years ago, when I was in Paris, I had to use computers in internet cafes. The possibility that my banking credentials would be intercepted by a keylogger was always on my mind. I came up with one possible solution for the problem of using secure credentials on an insecure terminal:
Summary: A secure website to change passwords for you.
My idea is this:
Make a website that can change passwords on your favorite websites (Gmail, your bank, and so on). Give this website a list of passwords and corresponding "change codes" to use. Keep this same list of passwords and "change codes" on your person. When you have used a password in an insecure, go to this website and click on the "Change my password" button. To verify that it really is you requesting the change (and not some random internet user) you would be prompted for your "change code". After verifying your change code, the website would change the password to the next password on your list.
Summary: A secure website to change passwords for you.
My idea is this:
Make a website that can change passwords on your favorite websites (Gmail, your bank, and so on). Give this website a list of passwords and corresponding "change codes" to use. Keep this same list of passwords and "change codes" on your person. When you have used a password in an insecure, go to this website and click on the "Change my password" button. To verify that it really is you requesting the change (and not some random internet user) you would be prompted for your "change code". After verifying your change code, the website would change the password to the next password on your list.


Comments
For low security stuff, I had an idea for an authentication mechanism similar to what Ham Radio BBS's use: basically you create a NxN table of random chars, print it out, carry it on a card or whatever, and when you log in the server asks you for some random chars from it, like {(2,3),(8,1),(9,9)} etc. Not terribly secure (listen long enough and you can recreate the table) but possibly "good enough" for low security applications.
I wrote a quick and dirty perl implementation of this once.
Your idea would probably be more secure.