The relay will be in the open position, from having been opened by the arduino due to the battery voltage being low. The user then charges the battery, and turns the device back on using the external switch. The arduino doesn't receive power as the relay is still in the open position.
You'll have to deal with the basic power-on logic no matter what hardware solution you choose. The whole thing depends on the processor running to keep the power-on. So, you'll bave to bypass the switch (manually or automatically with some sort of timer circuit) to "jump start" the thing and to get it running before you can keep it running.
A solid state relay or MOSFET are also very efficient, so those are other options for holding power-on with out constantly-energizing a relay coil. (But,you'll still have to "jump start" it.)