In the image you posted, the bigger puzzle piece is partly overlapping the outside border part of the puzzle-image. You'd have to be quite creative in Photoshop to cheat this and get away with it.
Don't you have the original image where it's not divided in puzzle pieces? Or where the puzzle is complete?

If u've got the original,.. model your own version puzzle (at least a look-a-alike). No one will notice it in an animation. If not ... hmm ... use it as imageplane to model the puzzle (?)
For texturing,.. I'd go with mhcannon's group-mapping solution.