I remember backpacking in Asia I kept a DSL bootable USB with me. When I'd visit a net cafe I'd simply boot into my DSL environment and bypass the entire windows PC (which was full of spyware and password stealing programs).

It worked great back then, I'm sure it works even better now.