This is the basis of my suggestions. Cutting power means you need a relay, which is going to draw 20-50mA continuously while the Arduino is powered up -- which by design is when the engine is NOT running, hence the battery is NOT charging. An efficient regulator and judicious use of sleep states will bring the idle consumption down considerably.
Besides, relays are ugly devices. There's back-EMF, mechanical operation, contact bounce, tarnishing and pitting on the contacts themselves, parasitic current draw while engaged... Having to engage the starter means having to use ONE relay. But I would not be in a hurry to add any more than absolutely necessary.
Now, you could use a normally closed relay for power, and open it only when the car is running. But then if you have a kill switch (to turn it off during periods of non-use, or for safety when you want to work on the car), your relay is energized again, wasting power.
Yuck. 