Well, if you really need to run at 5V and and want to recharge in circuit you can use something like this:http://www.sparkfun.com/products/10300
(You really need to check it out for yourself - I'm just putting out ideas.)
That board has pins for 5V input and a USB conn. But even if it had only a USB conn. you can use a wall wart that looks like this:http://www.sparkfun.com/products/10214
Your choice of battery depends -
- Your going to go with LiPo?
- How long must it run before it is put on charge?
- How much current does your circuit really
- Size issues? Cost issues?
Once you know the current and time between charges you can cal how many mAH your battery should be.
With the little bit of info I have here I'm really shooting in the dark here, so this is the best I can do.