My 2 cents, on the original question...
Buying a wierd/custom battery is not good, due to the uneven drain.
Regulating is the correct answer, but I would avoid linear regulators. If you lose 6V in the linear regulator (12V in - 6V out), and doing this at 4A, you're losing 24Watts in heat! That is significant!
Also, most 78xx regulators are rated for 1A (some at 1.5A), but that is with a lower drop voltage. Dropping 6V would probably cut you back to well under 1A, so you'd need more than 4 regulators. And to dissipate 24W, you'd need *significant* heatsinking, plus some type of air movement. And also make sure that the specific brand of regulators allow paralleling outputs.
The DC-DC converter is the correct answer. That Lineage Power dc-dc converter that Kevin pointed to is really nice for the price. Another option is to build your own, with the circuit designed for you automatically by one of the online switcher tools. One of my favourites is
National's Webench. Enter your requirements and it will select appropriate switching regulator IC's for you, and then design the circuit for you. You can then tweak component values and see how the circuit responds (regulation, efficiency, etc). You can usually even order a kit with all the selected components, but then it gets costly. There are other manufacturers that do this too, btw.
For your requirements, I'd think one of the ready-made dc-dc converters would be best, but look through the datasheets to see if they require any external capacitors, as some do.
Cheers,
-Neil.