Let's say your tile is 40x40 px.
Make horizontal selection with 40 px height and the width of your image. Position it at the top of the image.
Now record simple action consisting of two steps:
1. Filter->Other->Offset with horizontal offset value set to some multiple of 40 and Wrap around option checked.
2. Shift the selection one row down: just use Select->Transform selection with bottom reference point and -100% Height. This way you can use it later with selections of any size.
For Offset Filter step check "Dialog on" checkbox in the Actions panel. Choose some shortcut for your action.
Now start playing your action repeatedly, each time choosing some random offset of multiple of 40 in the Offset filter dialog. Once you've done all the rows of the image rotate it: Image->Image Rotation 90CW, again select the top row and play
the action again as many times as needed.
Finally rotate the image back 90CCW.
Instead of playing your action manually I'd suggest making special helper "Repeat" action, which just plays your action many times. Just create new action, call it Repeat and record one go of the action, stop recording. Then copy that step many times in the Actions panel(select the step, copy, select all copies, copy, select all copies, etc). By playing this Repeat action all you'll have to do is just enter the Offset parameter in the Offset Filter dialogs. Once your selection goes outside of the image it will show error message letting you stop the action all together.
If your not satisfied with the resulting look just rinse and repeat
P.S. If you have a hard time picking random numbers you can find many online random generators...
P.S.S. I'm pretty sure someone here can write a script realizing all of this this automatically...