I have got guidance on how to create a new Apple ID that wont use a credit card, but could not find a way to associate my existing Apple ID (with my main email) to App Store without inserting a credit card. I have tried the OS X App Store software, the OS X iTunes software, and logging into the Apple Site.
I believe this is the intended behavior on Mac OS X. On iOS, you can establish App Store use of an Apple ID without requiring payment information so you could borrow a friend's (or a store's) iOS device for a moment and just establish your account as valid for App Store use.
From there, you could of course load a gift card by redeeming it or just log out and then try again. This has worked in the past for many corporate ID where we didn't want to have billing information on individual accounts.
Lastly, the Apple support might be able to guide you if things have changed with them being more protective of accounts to prevent fraud, false reviews in the App Store or whatever else motivates Apple to change policy around the online stores they run.
There should be a payment type selector as "None" on your account setup screen. The only caveat is that the account needs to be created via iTunes in order for this payment option to show up. You can also find more info on this KB: http://support.apple.com/kb/HT2534
Logout of your account, then go to free apps, click install, then click create Apple ID