Normally, even though your card # changes, the account its tied to and any charges carry forward.

In the Hertz checkout system, we do not need to see the card you prepaid with. In fact, we don't see any card information on your pre-payment. When we check you out, we will see it kind of like this:

RATE: 100.00
ADJUSTMENTS: -100.00 (this is your prepayment)
SUBTOTAL: 7.00/etc (sales tax)

The only card needed when you check out will be for your deposit. I wouldn't worry about paying the fee to change the card number.