Cutting power to the Arduino seems excessive. I wouldn't do it that way. Just control the starter and ignition relays in a sensible way. Use a state machine to track your status (idle, starting, retry delay, running, etc..)
If you're planning to run the Uno (rather than build your own breadboard/stripboard Arduino), it has a regulator built-in. However, dropping 12-14v down to 5v (onboard regulator), or 12-14v down to 6v (external regulator) involves quite a bit of linear regulation. I.e., heat, and wasted energy. I don't know exactly how long it'll take to drain a car battery -- probably a while -- nonetheless, it's not optimal, and will get quite warm.
Don't cascade those regulators, btw, as 6v isn't a good margin for the onboard regulator. Although, I don't know how comfortable I'd be passing 6v directly into the 5v input either. Basically, the LM7806 is not a great fit here at all. No linear regulator is, in fact. I would strongly encourage looking into switching regulators.
Now, all of the above is nearly a moot point in that you need significantly more filtering to run reliably from an automotive power system than from AC, batteries, or USB. I posted in another guy's thread here about the ignition sequencing computer he wants to build. The gist being, car power is dirty. There are lots of articles and forum posts on the topic, so start looking into it before you button this thing up in your car. Consensus is, a simple regulator and protection diode are not adequate. Be prepared for high voltage (50v typical, 100v+ common enough) spikes, negative voltages (hookup errors or coil transients), brown-outs (starter), and lots of noise.
Don't forget a fuse!
Oh, and definitely don't hook up anything from outside your stripboard straight to I/O pins without protection. If you can't isolate it entirely, then current limiting, reverse-polarity protection, under/over-voltage shunts, an inductor (if you can low-pass your input signal that much) would all be a good idea.