Powering LEDs + a Controller with Lithium Ion Batteries
Cheap 3.7V to 5V voltage boosters that can do 2.5A are readily available. You might be able run several of these boosters, each one supplying power to a part of the circuit.  

However, while the Adafruit 6600mAh 3.7V li-ion battery can deliver a maximum of 13A (though not with the supplied cable and connector, which can only handle a mere 2 Amps!)  you need more. As the booster steps up voltage so its output current must drop proportionally. You want up to 12A @ 5V which equates to 60W. The booster cannot be 100% efficient, so it must draw more than 60W from the battery. For example a booster with 85% efficiency would draw 70.6W = 19A at 3.7V, way over the battery's rating. Also you will need thick wires and beefy connectors to carry this high current!

A better solution might be to use a higher voltage battery (eg. 7.4V) and step it down to 5V. That way the input current will be more manageable, and you can choose from a wide variety of high current buck mode regulators. At 7.4V you still want a battery that deliver at least 10A of real current. I would use an RC car lipo such as this 5000mAh 7.4V pack, which has 50% more energy storage capacity than the Adafruit 6600mAh 3.7V battery, and will have no trouble handling 10A.