Electronic – Desolder two PCBs soldered 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.

You might want to try with ChipQuik. It is a solder that has much lower melting point than your everyday solder. When you remove as much solder as you can, flood it with ChipQuik. Given enough solder, it should be possible to keep all points in melted state by reheating them in turn as they turn solid.

Once you do have them all melted at the same time just wiggle the board until you get it out. And don't forget to clean ChipQuik before you resolder things back in.