I rented it from Avis at Berlin-Tegel (TXL). The international reservations desk at the 800 number was able to take care of setting it up without too much trouble. If you call you need to make sure to tell them where you want to go and that you need the insurance (which you do). They were able to get me a great price that included all of the necessary insurance.
d