When the arduino senses the ignition wire is energized, it releases the relay.
This is what I would do. That, or use the ignition as a sense pin and have the Arduino always control the relay. I.e., start the car by closing the relay. Open the relay after 10 minutes. Cancel the kill timer if the key is inserted, and immediately open the relay if the key is removed.
For the engine start, you could try 1200ms, check engine pulses or battery level (both good ideas!), then delay for a few seconds, try again, check, delay, try again... After maybe four attempts, give up.