Encryption requires a secret to work; anything else is just obfuscation, and wide open to anyone who knows the algorithm being used. You don't have to exchange long-lived shared keys, but alternatives (RSA, OTP, etc.) tend to require a preexisting trust relationship and/or secure channel.

Furthermore, the only way in which WEP or WPA improve real security is by keeping folks who don't know the key off the local network. Since most shops freely give away their network keys to anyone with enough cash for a cup of coffee, and seldom if ever rotate keys, it's an awfully weak level of protection.

If you assume that other network users are potentially hostile, and/or that the coffee shop owner (or its ISP, or someone who "hacked" their Linksys router via an unchanged admin password) can't be trusted, your only real option is routing your traffic over VPN to a trusted host elsewhere on the 'net.