I got another idea. As you mentioned to use a prepaid visa card for buying stuff. Why don't use a prepaid umts card for internet access? If you buy the card and the voucher with cash then nothing points to you. Of course you should travel with this card to make sure to not use the same radio tower all the time. Maybe someone can make a localization profile or such things. But I don't think you need to worry about that to much.
