The Solar Idea is OK, but just use rechargeable NIMH batteries instead of Lithium Ions.
NIMH batteries can withstand overcharging without damage provided that the charge current is C/20 or less.
Using 6 AA 2500 mah batteries will provide between 7.2 and 8.4 V which is just enough for the 5V regulator on the Arduino board.
If you want plenty of battery reserve for cloudy days , then use C size nimh batteries.