Get an itunes gift card or there should be a NONE option along the visa, amex, line. If u have an AppleID already, then just go to iTunes on you computer and on the left column click on iTunes store, then on the upper right hand side of your iTunes store window and click on your email or sign in first. Enter your password and View Account. Make sure that your payment is set to NONE then DONE.
Ok, so here's what I did (iPad 3, Win7):
1.Created a new email account (gmail, to be precise)
2.Opened iTunes (on PC with Windows 7)
3.Browsed for free apps
4.Tried to download one (Bubble Explode)
5.After a message popped up I chose to create a new Apple ID, as the location I typed NY, United States
6.The 'None' payment option did appear
7.I finished signup and downloaded the app on PC
8.Signed in on my iPad 3
9.Deleted the app and signed out on PC
10.Connected to AppStore on the same iPad
11.Downloaded Bubble Explode via iPad and deleted it after it's done
Be patient, for me it took 3 days and I was furious as never before in my life since Windows Vista.
Feel free to ask if sth. is unclear and remember that just because I made it, it doesn't mean I can do it once more.
What I did as I was having this problem also.
1. Plug your phone into itunes
2. create the acc as per normal
3. when it ask for cc info
4. click your phone and begin the setup on your phone.
5. once set up is complete then go to app store
6. purchase free app.
7. it will ask you to review your account
8. click review
9. then it will prompt you with cc options, where the option NONE is avail.
10. this works, only on the IPHONE not on your itunes on the Computer.