How can I regulate a 5V battery?
Since you can't do anything about your power source, then you should try your idea of a boost regulator.

You don't need to boost the voltage above 5v and then regulate it back down as you suggested; instead you can just boost it up to 5v using a boost regulator like the ADP1613 which will take any input voltage from 1.8 to 5.5v and regulate it to an adjustable voltage up to 20v, but in your case you will set this at 5v.

You can get the part at Digi-Key for $2; plus you will several external components.  Unfortunately all of the boost regulators with the current requirements you require (~1A 5v output with 3v input) are only available in surface mount packages; this one is 8-MSOP which can be hand-soldered fairly easily.

Your battery pack has plenty of capacity (10.4 Ah) so it should be able to power your circuit for several hours.