Hm, brauchst Du lange Laufzeit?
Auf der einen Seite verbrennst Du im Arduino 7/12 deiner Batterieenergie. Auf der anderen haben Batterien eine Entladekurve, so dass Du bald erheblich unter die 12 V fallen wirst.
Ich würde einen 8MHz Arduino direkt an einem LiPo betreiben (über den 3.3V Pin) und einen Stepup zu 12V verwenden (wenn das mit dem Strombedarf des Selenoids hinhaut), den ich nur aktiviere, wenn der Selenoid gebraucht wird (enable pin oder MOSFET davor)
Der hier geht wahrscheinlich: Pololu 12V Step-Up Voltage Regulator U3V50F12