When are you being asked for billing info, and are you getting an error message if you leave it blank ? And when/how did you create the account ?
Unless an account is created by following the instructions on this page : http://support.apple.com/kb/HT2534
then credit card details will need to be entered before the account can be used in the stores.