Update (March 6th 2014): Numerous comments say this method works; added strikethrough over the previous update.
Update (April 1st 2011): Apparently this method no longer works. Try using it, but when I tried using it a few minutes ago on a friend's existing Apple ID, it did not work. It might work when you create a new account. If it does, please come back and leave a comment.
If you try turning on Genius in iTunes, you'll be prompted to create an account where in last step you need to enter payment information. If you don't have a credit card follow these steps:
1. Instead of going to Genius, go to iTunes Store.
2. Try downloading one of free iPhone apps.
3. When you're asked for account information, click Create account.
4. Fill out the forms as usual.
5. On last step, you can now choose None as payment method (as opposed to creation through Genius).