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.