If you can't use a standby battery then the only thing I can think of is another relay connecting to the car battery with the relay controlled by the Arduino and by the main relay. When the main relay shuts off power the Arduino will continue to draw power through the second relay while holding the relay on. When it is time to quit the Arduino will disable power to the coil of the second relay.
For starting up the main relay will allow power to the second relay's coil thus energizing the Arduino.
Be sure to put suitable fuse between the second relay and the battery, as close as possible to the battery, or to the point on the electric system from which you draw power for the second relay.
Could you use 3 x AA alkaline cells for backup power. If they only need to power the Arduino for a few minutes at any one time they would probably last for months before needing to be replaced.
HeliosPrime:
How would the Arduino know when the ignition controlled relay is no longer energized?
Good question.
You could put a voltage divider on the power line from that relay and connect the divided voltage (not more than 5v) to an I/O pin and then check with digitalRead(). You will probably need a diode between the main relay power and the power via the second relay so that the second relay does not back-feed to the line with voltage divider.
A better way would be to use a 3rd relay that is only energized by the power from the main relay and whose contacts connect the Arduino 5v pin to an I/O pin. That way there is no risk of stray high voltages from the car system getting to the Arduino. Or, rather than use a 3rd relay you could rig up a simple single transistor circuit that does the same job.
...R
PS... if you are designing a voltage divider allow for the fact that the car voltage may sometimes be as high as 15v.