If it was me, I'd just use a 4 pack of AA NiMH batteries. The PIC will run just fine on full charge (almost 5.8v) down to practically dead (figure a bit above 3.6v).
The LCD should operate just fine in that range also. I don't know exactly which LCD you've got, but I know my parallel types run down to 3.5v ok, only problem is the screen wants to update just a bit slower and the contrast changes a bit.
As for the wireless module, again, haven't looked at the datasheet. I may very well be 5v tolerant. If not, power it with an LDO 3.3v regulator or maybe an inline 1N4004 diode to drop the voltage by about .6-.8v.

As far as charging, find a suitable voltage output wall wart, say a 9v charger. Take your battery pack capacity, say 4x AA NiMH rated at 1800mah. Put in a polarity protection diode in case you plug the charger in backwards, and add a series current limiting resistor to keep the batteries topped off. In this case, max battery pack voltage will be around 5.8v as stated above. An 1800mah battery pack probably shouldn't see more than 1/10C when almost depleted and 1/100C when charged up (to keep the battery pack living longer that is).
So, that being said...
9v input minus a diode drop 9-.6 = 8.4v.
An empty 4 cell battery pack is about 3.6v charging at no more than 1/10C (180mah).
(8.4v input - 3.6v battery voltage) / 180mah = 26.6 ohm series current limiting resistor.
When the battery pack gets fully charged, this same current limiting resistor will limit the charge current to:
(8.4v input - 5.8v ) / 26.6 ohm = 97.7mah -- a bit too much (about 1/20C).
This will give you about a 12-13 hour charge from completely dead. But if you're like me, you'll forget about the charger quite often, so I'd go with the other end of the spectrum:
(8.4v input - 5.8v charge pack ) / 18mah = 144.4 (give or take) ohms.
With the 144 ohm resistor, you'll get the 1/100C rate at the end of the charge. Completely safe for NiMH batteries, but the downfall is that it'll take a few days to put a completely full charge into the batteyr. I've been using the 26.6 ohm resistor method above in my mp3 player I built for about 2 years now on the same pack without a problem. You might want to use anything between 47-120 ohms, take your pick. It's all about ohms law...

Personally, I think you're overdesigning the project. Don't get me wrong, not a bad thing, but sometimes...simple is best... Stay away from Li-Ion for now. They're not really hobbyist friendly quite yet...especially not for a beginner anyways...or even a well-versed amateur like myself.

JDG