I played with paths and 2D graph approximation to create a random jigsaw puzzle shape. The result is here: http://secretpaste.org/puzzle/pic1.html
Currently this is considered a beta. It is and will be free to use. Parameters control the picture and number of tiles. Just have a look at the HTML code.
DiTo: I hope you don't mind I use a picture you posted here. If you have any objections let me know and I'll replace it.