[Piwoslaw]

Teoman, since you are going to purchase a new (to you) car anyway, look for one that is white or silver. Also you may look into coating the windows to reflect infrared to keep the greenhouse effect down.

Insulate the bottom of the car also, to reduce gain from the hot pavement.

Park in the shade when possible, schedule your driving for when the temperature is lower and the sun not as intense.

Driving down a local road, in the shade of trees, may be better than on a highway with no shade at all.

Roll down windows after getting into the car to naturally ventilate the excess heat.

A reservoir can store some "cold" for you, but it has to be "charged" first. If you have the means to cool the liquid at home, then great. Phase-change materials (like ice) would work even better.

A larger condenser will only work if you have enough air flowing over it. And to get better airflow, you are sacrificing aerodynamics, which will further increase your fuel consumption. If your airflow is good, then you may experiment with spraying (distilled) water on the condenser. There are a few threads on EM about this.

You may look into A/C run off of electricity, not off the engine, like in hybrid cars. You may need an extra battery, which you could charge at home.

Engine braking is a good idea, but won't be easy to automate. You can try to a programmable OBD device (like OBDuino) to turn on the A/C only when the engine is running but no fuel is being used. (This idea came up in a discussion about automatically charging the battery in an alternator delete scenario.) Do take into account that the A/C compressor prefers long on and off durations, so quickly cycling it on and off will shorten its life.

When you do use A/C, make sure that your ventilation system is in recirculating mode (to not be constantly warming the outside air) and the fan in on HI (to increase the efficiency of the heat exchange).