I had the same problem trying to download French apps to my US registered iPad. I literally had to go to France and purchase a French iTunes giftcard, so I could set up my store preference with a French address and French payment method.... Just so I could download a few free apps. The one that I really wanted (radio and TV app) now stopped working when I am in the US
I could not find a way to get a French iTunes giftcard online.
The good thing is that you can buy something like a US Visa prepaid card online for sure, have you tried that? I could not find a way to do that with a French prepaid cc. It may be even possible to purchase US iTunes giftcards online.