How about decoupling capacitors for the iPod?
Capacitors basically resist voltage change, so you could design a device which will go in between the iPod and USB cable and have some decoupling capacitors which should be strong enough to power the iPod while the car is starting.
You could have one male and one female USB port on the device and put the capacitors between the GND and +5 V pins. The data pins should be directly connected between two plugs, because iPods may need some circuitry there and since the charger does work, it would be best to use its circuitry for that. Here's USB pinout.
From what I've read, if we have 3 V of ripple when the car is starting, 2200µF electrolytic capacitor would probably be enough for full USB 2.0 load, but I'm not too sure. For voltage rating, I'd take at least 25 V, but more is better in that area. You could also look for low ESR capacitors. They should work a bit better. Some people say that it's a good idea to put in parallel capacitors of several different values, because they all block noise at different frequencies.
Another option worth considering is to get Toyota's iPod connector, but it's going to be more expensive and defeat the purpose if having a hack.