You can do it like this with bash and ImageMagick:
#!/bin/bash
convert -crop 16x16@ input.jpg tile.jpg
montage -geometry +0+0 $(ls tile*jpg | awk 'BEGIN{srand()}{print rand() "\t" $0}' | sort -n | cut -f2-) output.png
# Remember to remove the tile*jpg before you do another one :-)
# rm tile*jpg
Basically as you suggest, using -crop and montage. The bit inside $() is process substitution and it takes the result of running the process inside the parentheses and puts it into the montage command. It lists all files called tile*jpg and pipes that into awk to append a random number to the front of each file, then it sorts by the random number and chops it off.
So it makes this:
into this:
I have been experimenting further with this (i.e. playing around) and I see you can get white lines and gaps between the tiles. I am not sure if these bother you, but if they do, a possible solution is to note the original image geometry and then resize it to an exact multiple of your 16x16 tile-size. Then proceed as before, and resize by the odd 0-15 pixels at the end, back to the original size.
If that is necessary, I came up with this:
#!/bin/bash
# Get original image geometry
origgeom=$(identify -format %g input.jpg)
echo $origgeom
# Calculate new geometry as exact multiple of tilesize
newgeom=$(convert input.jpg -format "%[fx:int(w/16)*16]x%[fx:int(h/16)*16]" info:)
echo $newgeom
# Resize to new geometry and tile
convert input.jpg -resize $newgeom -crop 16x16@ tile.jpg
# Rebuild in random order then correct geometry
montage -background none -geometry +0+0 $(ls tile*jpg | awk 'BEGIN{srand()}{print rand() "\t" $0}' | sort -n | cut -f2-) JPG:- | convert JPG: -resize ${origgeom}! output.jpg
