You could boost 2.4-3.6V from AA's (NiMH rechargable) to 9-12V, then a small 5V linear reg for the PIC. I mean its more hassle, more money (to buy a module) but its perhaps another solution to think about
Or of course, battery voltage to a stable 5V, then yet another boost to 12V - but two converters in series, lowers efficiency and is even more hassle.
Something like this, which are all over ebay:
**broken link removed**
Granted, they are cheaply made, so their rated efficiency is usually over stated. But they'll work, and you may be able to up the output voltage so it can run from 2-4V, and output 12V for your LED's, then a simple 7805 to the PIC.
Of course, the DIY approach will give you greater felexibility, but more hassle in terms of making another 'piggyback' PCB. You mentioned your peak current requirement for the 12V line was 0.43A. Thats quite a bit of power - over 5W, a PP3 9V would definately struggle with that, and whilst AA's can kick that out, getting a boost converter to handle that much power from a low voltage source is tricky. With 9V your peak current was 0.19A ? 1.7W thats a lot lower.
If the higher voltage is only for the LED strings (in series) then it *may* be more prudent to buy premade LED modules, designed to work from 5V DC, that have on board boost converters specifically for the LED strings. It'll take in 5V and some form of PWM control (from your PIC) and may be more efficient. That way you only have to provide 5V to the entire system.
Note: I do tend to grossly over engineer things sometimes. Powering things with batteries brings several restrictions to the table, power consuption, battery life, battery voltage (which drops as the battery discharges), size, weight.... cost. The reason AA's are mentioned is that for their size/weight, they have much greater power density than PP3's - which can't provide much current, and their voltage drops to ~7V rather quickly. And rechargable batteries can kick out virtually their entire capacity quite quickly, providing several amps over as little as 30 minutes, because of lower internal resistance.
How small must this battery be? In the modern age of mobile phones, mp3 players etc.. one can usually find batteries used for products as replacements all over the web, ebay, amazon etc.. whilst they wo'nt be 'standard' like AA, or PP3, they may suit your purpose if they are rechargable.