I think your project would be much simpler if you use a decent sized lead-acid battery. With a small solar panel you would probably need no regulator circuit just the diode to ensure the battery doesn't discharge inot the panel.
Whatever battery you use you will need a solar panel that produces more volts than the battery voltage. You will also need to estimate (and be pessimistic!) how many milli-amp-hours your circuit will consume in 24 hours and how many mAh the solar panel will produce taking account of whatever local weather conditions affect the amount of sunshine. The battery has to have enough capacity to deal with a succession of days of poor sunshine. If you need the device to work in winter you will have to take account of the shorter days (less sun) and longer nights (more Arduino activity). That will need a much bigger solar panel than you would need in summer time.
Try a second-hand 12v car battery?
...R
...R