I've never tried it, but there's a special desoldering alloy called Chip Quik which lets you desolder ICs with a normal soldering iron. It has a very low melting temperature, so you can apply it to all the pads in turn with your iron, and they will stay molten long enough for you to reach all the pins and remove the part.
The guy in this video used it to desolder a 160 pin chip from a Nintendo 64: