When I travel, I initially give my "backup" credit card for the deposit purposes. I carry no balance on this card, and use it only for real emergencies, so the loss of available credit is not at issue for me. I then offer my "payment" card at return, and pay the bill. Takes maybe 5 minutes longer.

Honestly, do you carry that large of a balance that an extra $100 would make a difference?

And lastly, if it does, rent with Alamo/National who only hold the price of the rental.