If you want to stick with relays, you could use dual coil latching relays, they're a bit more expensive but once you set them, they remain set without consuming power.
An example :
https://www.lcsc.com/product-detail/Magnetic-Latching-Relays_HF-Xiamen-Hongfa-Electroacoustic-HF115F-LS-12-HSL2F_C190453.htmlYou have 3 input pins 1 ---- 2 ---- 3 ... you put your voltage (12v for this relay) on pin 2, and if you want to turn on the relay you connect 3 to ground for at least 30 ms , and if you want to reset it you disconnect 3 and connect 1 to ground at least 30 ms.
So you could have a small step-up converter boost your battery voltage to 12v and supply just enough current to power each relay for let's say 50-100ms at a time ... the datasheet for the above says 0.6w power consumption, so you'd need a minimum of 0.6w / 12v = 0.05A (50mA)
if you want you could store the state of each relay in a fram memory chip or maybe an eeprom (but an eeprom has fewer write cycles) in order to remember how the relays are configured if there's a power loss (battery too low for example) but I think it would be too much of a bother. You could just periodically check the battery voltage and when it goes below 3.5v you could just reset the relays one at a time and stop working until the battery is charged again. Also, at each startup, you can reset each relay one at a time to make sure each relay is in a known state.
Because the coil current is lower than 100mA, you could use a mosfet array like let's say ULN2003V12 (just like ULN2003A but without the big 1v drop on each channel) which contains 7 mosfets and all the resistors and ESD protections and even the diodes you'd normally use on each relay coil (1n4007 in your schematic). I would still have those 1n4007 diodes external though, they're cheap.
ULN2003V12 :
https://www.lcsc.com/product-detail/Darlington-Transistor-Arrays_Diodes-Incorporated-ULN2003V12S16-13_C148113.html?s_z=n_uln2003v12It says darlington array, but it's really mosfet array with 7 channels. You could use only 6, to control 3 relays (2 channels per relay, one to turn on , one to turn off)
So with these changes you'll only need to have a step-down regulator to reduce the voltage from one battery (for example a 18650 lithium cell) to 3.3v you need for your arduino, and the step-up regulator will just idle until it needs to power a relay coil for 30+ ms at a time.
use something better than lm2596 for step-down regulators .... see for example AP61100, very simple to use (though it's a bit small) :
https://www.lcsc.com/product-detail/DC-DC-Converters_Diodes-Incorporated-AP61100Z6-7_C1858397.html?s_z=n_ap61100But it's almost not worth it, considering your arduino is gonna consume only a few mA... so you could use a cheap LDO like for example XC6206-33 (fixed 3.3v version) :
https://www.lcsc.com/product-detail/Voltage-Regulators-Linear-Low-Drop-Out-LDO-Regulators_MSKSEMI-XC6206P332MR-MS_C5252899.html or HT7533:
https://www.lcsc.com/search?q=ht7533These regulators have a dropout voltage of around 0.2v at 100mA, so will work pretty much down to less than 3.3v input (your arduino will function with less than 3.3v)