I'm looking to buy or build a device that would prevent my in car arduino Project from killing my battery.
To make it smaller and cheaper you could use a low current voltage detector like the microchip TC54VC2102EZB and feed the output into an N chanel mosfet to switch the power from the battery. To use another 328 will merely drain the battery even though the main circuit is switched off. You need to make sure your detection circuit does not drain your battery while switching off the main device. The TC54VC2102EZB above draws an operating current of 1 uA.
Once the voltage drops switch the n chanel mosfet on which switches the relay off.
Try this setup (anyone else feel free to chip in with improvements).Get the nearest value resistors for the divider as these are theoretical values.You need to minimise the current draw through the divider but still maintain enough curreent for the TC54. See the datasheet.I would put a trimmer pot in instead (although this is not considered kosher) with the wiper pin to Vin of the TC54 and the outer pins to the + and - and then you can have infinite control of the divider. Check the temperature on the arduino linear regulator as at 13+ volts it may be getting too hot. You may want to put in another regulator/DC-DC converter prior to the arduino. Edit:Just noticed your hysteresis requirement (12v cutout, 13.4v startup). You can lookup LM393 circuits with "hysteresis" in the search. Substitute this for the TC54 although it pulls 0.4 ma which is much more than the TC54.
Explain how the relay shield , Fob, Arduino, and cellular shield are meant to interact and what you are trying to achieve. Do they only activate when the ignition is on or do you need them always active (listening)?