I *think* this should do it using radioshack parts. The cap is kinda expensive, I just grabbed the biggest one they had to help address the resets.
You probably won't need an extra regulator with this, as you have a voltage drop in the diode and the 8 ohm resistor.
So when you start the car, the idea is that this will help maintain a higher voltage for the guino. Dunno if it will help though. If you can salvage a 25v (or higher) large cap that would be cheapest.
4700µF 35V 20% Axial-Lead Electrolytic Capacitor - RadioShack.com
4700uf axial cap
1N4001 Micro 1A Diodes - RadioShack.com
1n4001 diode
8-Ohm Non-Inductive Resistor - RadioShack.com
8 ohm resistor