Soldering PCBs directly together
No problem. I had to look for a picture that illustrates the technique:  



You make a PCB with plated through holes on the PLCC's pads, so at a 1.27 mm pitch, and mill the four sides so that you get the half holes like in the picture. These are easily solderable on the old PLCC footprint, it's an often used technique, called castellation. 

A picture of a complete board:  



and another one:



or this one from a question posted 1 minute ago:  



You get the idea.

You'll have to find a part which fits inside this small PCB, but given the miniaturization of the last years that may not be a problem.  

edit 2012-07-15
QuestionMan suggested to make the PCB a bit larger so that the PLCC's solder pads are under it. For BGAs the solder balls are also under the IC, but that's solid solder balls, not paste, and I don't know how solder paste will behave when squeezed between two PCBs. But today I bumped into this IC package:  

  

It's the "Staggered Dual-row MicroLeadFrame® Package (MLF)" of the ATMega8HVD, and it has pins under the IC as well. This is 3.5 mm x 6.5 mm, and weighs a lot less than the small PCB. That may be important, because thanks to the low weight capillary forces of the molten solder paste can pull the IC to its exact position. I'm not sure if that will also be the case for that PCB, and then positioning may be a problem.