Sounds like a very cool project!
The TinyDuino can use and charge standard 3.7V Lithium-ion / Lithium-polymer batteries. We'll eventually have more options, but you can definitely use a larger battery (Sparkfun and Adafruit both have many options). You will either need to solder the battery into the board, or cut the connector off of one of our batteries and solder it onto the new battery.
Thanks,
Ken
TinyCircuits