This question is about paying the car hire fee only, not about making the security deposit (for which a credit card is understandably required).
Context: at least one Australian car rental company is applying mandatory credit/debit card surcharges. Your rental agreement says that the hire charge is say X, but in fact you have to pay 1.011 * X because of the surcharge. This is in their T&C, and their FAQ says that they won't take cash. They take cards only, and all card types are accepted with a surcharge.
Is it legal for them to form a contract for one amount, but only accept payment methods which result in paying them a higher amount?