Arduino remove power if battery voltage is too low
You are correct - you can't use the Arduino to do it. You'll need to make a separate voltage monitor/control circuit which does nothing but watch the battery. In principle, something like 







simulate this circuit &ndash; Schematic created using CircuitLab

will work. 

For this circuit, CMP1 is either a comparator or a rail-to-rail op amp which can operate at low voltages. D1 is either a zener or shunt regulator which gives a voltage of less than 3 volts (2.5 is common enough). M1 is a PMOS MOSFET with a low gate voltage requirement (well under 3 volts, and less than 2 would be better) as well as a low enough ON-resistance ($V_RDS(ON)$) to avoid much voltage drop at the Arduino. R4 is important to establish hysteresis - otherwise when the Arduino is turned off, with no load the battery voltage will rise, turning the Arduino back on, dropping the battery voltage and turning the Arduino off, etc.

The biggest problem with this setup is that it will constantly drain the battery, with the voltage reference, R1/D1 being the worst offender. But there is really not much you can do about it.