Personally, I would reduce the power requirements as much as possible.
Firstly, I'd be inclined to convert the Arduino to run on 3.3V instead of 5V - it's more efficient.
(and make sure you use a low-dropout regulator)
I'd then run the system on the 3.7V LiPo.
This I'd charge from the solar panel through a switching buck regulator and associated LiPo charge management circuitry (say a BQ2000 based circuit).
To be even more efficient I'd also consider scrapping the Arduino altogether and maybe using either the bare Atmel chip with the most basic circuitry required to get it going running at 3.3V, or switch away from the Atmel altogether and go for a super low-power chip like the MSP430. Of course, the latter would then mean that you'd have to re-write everything from scratch, and you'd no longer be eligible for help from us ;)