Rechargeable battery type recommendations for a 1-2 amp bicycle LED circuit
(This answer summarizes Anindo Ghosh's suggestions on the topic made in EE chat plus a few of my own observations. Please note that I am not considering this answer definitive: just want to add something else to the mix of suggestions)

This answer assumes (without justification) a LiPO battery-based design. Some background information:


LiPO battery cells are 3.7V
Connecting battery cells in parallel is undesirable because if one battery has lower internal resistance than the others, the first battery will discharge first and then the other batteries will begin charging the battery with the lowest internal resistance.


The recommendation suggestion is to split the circuit into the following parts:


5V circuit: for the ATmega and all the LED drivers.  This part will be driven by a switching boost regulator to step up the voltage from 3.7V.
Separated the LEDs into banks such that each bank is driven by set of serially-wired LiPO cells: this avoids having the LiPO cells wired in parallel (more on the reason for serial wiring below).


Since the TLC5940 is a sink driver, the LEDs can be wired at whatever voltage. Because these are RGB LEDs the \$V_{forward}\$ of at least some of the green and blue channels can be as much as 3.4, leaving only 0.3 V of headroom assuming given LiPO's nominal voltage. Adding the fact that LiPO voltage varies substantially over the discharge cycle (Wikipedia: "The voltage of a Li-poly cell varies from about 2.7 V (discharged) to about 4.23 V (fully charged)"), this is not sufficient. Furthermore, according to Anindo Ghosh and a TI thread, TLC5940 requires a good amount of headroom over the \$V_{forward}\$ voltage to properly regulate the LEDs: \$Vcc_{LED}\$ must be greater than \$Vforward_{LED}\$ by about 1.2 Volts at 120mA sinking current - see Figure 5 of the datasheet. This leads to the conclusion that each LED bank must be driven by two LiPO batteries which will yield a minimum 5.4 volts to drive the LEDs; after the \$V_{forward}\$ drop of 3.4 V there is still 2V of headroom left.

A possible alternative to consider is witing R, G, and B channels differently: since the R channel has lower \$Vforward_{LED}\$, it may be wired from a single LiPO cell, while G and B channels will still be powered by two serailly-connected cells.

Finally there was a suggestion to consider LiFePo4 batteries, which have tighter output voltage over the discharge cycle, offer longer cycle life and higher peak current.