There is no way you can control the external IP address of a public network. Hell, even on your own network, you can only reboot your router/modem, and if you've got a dynamic IP, you should get something different.
Your options are to either use a different public wifi connection; to use a proxy (you can find a few fast ones around); or, the best option, which is to use a VPN. If you get a commercial VPN package, you're going to get good speeds from it (especially if you use a nearby one, rather than another country), and this will give you the different IP address you want.
A VPN will slow you down, but not as much as most of the publicly available proxies will. You've just got to face the fact that you cannot have anonymity and top speeds at the same time. If you actually care about changing your IP, you'll be willing to take the speed hit.
Exactly how you connect to a VPN depends on which distro you are using. Here are some instructions for Ubuntu, if you need a different distro, either google for them or adapt the ones here.
Any free VPN service you get is going to be slow, limited, and probably logged. A quick google search found that AlonWeb is somewhat recommended, and can be easily used from Linux with these instructions. As I've said before, it's not going to be as good as a paid VPN, if you can get it working at all. Do no rely on something like this.