Battery capacity is probably one of the hardest static quantities to measure in electronics.
You can try one of those "coulomb counters" or make something yourself after some testing based on the voltage measurement and temperature measurement.
For an Li-ion battery, the open circuit voltage is a somewhat good indicator of the state of charge (SOC) which tells us how much charge is left in the battery. You application though may require a constant run time so you cant stop to disconnect the battery and measure the voltage.
What else we know for sure though is that when the battery runs down under load, the voltage drops little by little, until it reaches the breaking point and then drops quickly.
This means that ideally you could measure the voltage over one run and then store the voltage readings, then determine what voltage you want to cut out at or start charging again.
The algorithm however has to be adaptive because as the battery ages the voltage will come down faster after a full charge. So you'd have to store some values and determine what voltage you need to start charging at again, or just when you need to replace the battery.
Temperature could affect the battery voltage also if it changes enough, so you may have to account for that also.
What we end up with though is something that might work, if we have a well behaved battery cell. But what if the cell starts to die prematurely? We need a better way.
A more reliable method would be to do something like the above, perhaps simplified, and provide a second battery to act as the 'backup' battery, that is kept fully charged and used only once the first battery runs down to a certain voltage level. The second battery kicks in and takes over, then the first battery is charged. Once the first battery is charged then it can be switched back over to using that one, then the second battery is charged back up again. Of course the batteries need to be sized accordingly.
Good luck with whatever you end up doing :-)