I would call or email Amazon customer service about it. It doesn't seem like you should have to have a credit card just to register a Kindle and get free books, but I'm really not sure.
The only problem with pre-paid cards is they charge you a monthly fee. My husband uses them to play poker on online gambling sites becasue we don't trust them with our real card numbers. He got his from Walmart and I believe it was $3.50 a month to keep it active. It would be cheaper to just open a bank account with $10 or something just to get a debit card.