Just keeping this thread going and pointing to the apparent "solution" that is buried in here somewhere (actually was a link from a MacRumors forum post):
To download a free app from the Mac App Store without a credit card, you (apparently) must create a new Apple ID, apparently from within the App store.
On your Mac, go to the app store and locate the free app. Click install.
In the Apple ID window, click Create New ID
You have to use a different e-mail address (and you will have to verify it) and create a password. You have to supply birthdate.
On the billing information screen, there should be a "None" button at the top. Click it. You will still have to provide an address and phone number.
I tested this various ways, including with an Apple ID I had just created on the Apple Store Web site.
This is TRULY a hassle. We'll see if it works when I want to get some other free app.