Latching relay - Remember state after power failure
Not sure why you would want to go down the path of latching relays.
You have an Arduino that when powered on can turn the power to your devices on and off ....you also have EEPROM in your Arduino, so could save the current state of devices to EEPROM. 
And when you startup after a power failure...if there are values in the EEPROM....restore them. 

You might want to consider whether you restore all values or just selected items since you may have power failures when you are not present....just a thought.