In Canada, the debit card system is different. The debit cards themselves are issued directly from the bank, with no Visa or mastercard type logo on it. The money that you use comes directly from your bank account, and in order to use it, you require a pin number and the appropriate "interac" machine to do so. You cannot purchase anything online with a debit card. Our credit cards that we get we can get at any bank without even having an account there. These include Visa, MC, AE, etc. I have only been to a couple of stores within the US that allows our Debit cards to be used there, but the bank fees are very high.
As for the original question, I do not know of any car rental companies within the US that will reserve a car for you without a proper credit card. Unfortunately, they require one for after as well in case you make dents, or damage the car in any way. that way, they are able to charge your card directly. This is something you agree to when you sign everything.
Jo