Considering the freezing points of sulfuric acid (283 Kelvin) and water (273 Kelvin), I would expect that the ions are the only things keeping the battery from freezing. I cannot say for certain, but it is possible that lead acid batteries could freeze when the temperature drops to 254 Kelvin.
A possible solution could be to use a different battery chemistry. Lithium Ion batteries freeze at 233 Kelvin, but they lose their capacity as a function of time and the ambient temperature. Given how hot it can be in the hood of a car, Lithium Ion batteries are probably not a good choice. There are other chemistries that are avaliable, which you can read about on wikipedia.
Another possible solution would be to insulate the battery, although a potential problem with that would be that the maximum temperature that it would encounter during the summer would be increased, so partially insulating it might be preferable.