The next best thing is some sort of two-factor authentication. Many services offer this these days (Google, eBay, some OpenID providers, like Symantec's (ex-Verisign) Personal Identity Portal). Depending on one's needs, this doesn't even involve carrying a RSA SecurID token in your pocket. It could just be a soft token on your phone that generates time-sensitive codes. Logging into an account then typically requires your password (one factor) and something else. Something else involves a factor that is different in nature from the first one. The different categories include knowledge (like, your password), possession (a token that generates codes or holds a cryptographic key, for example), and a person's individual properties (such as fingerprints or the iris pattern of your eye). But I divert. Really, in my internet cafe scenario, two-factor authentication is just a means to an end. I care less about having two factors, and more about having any factor at all that cannot simply be recorded and reproduced without having my token or my biometric properties. The problem with this is that biometric authentication isn't ripe for use over the Internet, and that I don't necessarily want to drag an (electronic) token of some fashion on the trek with me.
So, one-time passwords. A list of passwords that can each only be used once, and can be carried around on a piece of paper. My mail host, Tuffmail, which I love for its reliability and geek factor, doesn't support any. My backup solution for accessing emails while traveling in remote parts of the world is forwarding my email to Gmail, and (mis-)using Gmail's two-factor authentication.
You should use Google's 2-step authentication anyway. (Enable it in the authentication settings.) With that comes a list of "Backup verification codes", 10 of them, that are - essentially - one-time passwords that can be used in lieu of the regular second authentication factor. (In other words: if you aren't carrying your phone with you or don't want to pay for receiving text messages abroad.) So, you've got ten logins to your Google account with your regular password and one of the backup verification codes each. If somebody intercepts a logon on a borrowed computer, they won't be able to re-use those credentials after you have logged out. Without the second factor, your password won't help them. (Make sure you uncheck the box that designates the current computer as a "trusted" computer when logging in. And change your regular Google password when you get home.)