Single cells out of any laptop battery pack are chargeable by any 18650 charger, usually found quite easily in the various chinese stores. i use one from dealextreme for my cree flashlights, and it works really well (not too fast charge, doesnt overvolt cells, ends at 4.2V spot on.)
You could pack two cells with some heat shrinking material, and add a small dc dc to dc converter to drop down the 7-8.5v the cells will give you to the normal 5V the cellphone uses. Perhaps, also add a balanced connector port for safer charging, like LiPO packs do have. Remember those cells dont like being shorted, and never discharge them below ~2.7V.
The whole thing being built would be quite small, 7x4x2cm for the battery pack, plus something for the converter.
A good, well made circuit could even fit in a 2x4cm board sitting on top of the batteries. Take a look at maxim / linear's ics, quite some good stuff there.