PowerShell 6, 244244 254 bytes
De Bruijn sequence is a good idea. Thanks to Level River St
param($w,$h)for(;$z='A'..'Z'|?{"Z$x"-notmatch-join"$x$_"[-2..-1]}){$x+=''+$z[0]}$v=random 9 1..$h|%{$y=$_+$v ,(($r=1..$w)|%{"\ $($x[$y+$_-1]) /"})+,($r|%{$x[$_-1]+' X '+$x[$_]})+,($r|%{"/ $($x[$y+$_]) \"})|%{$_-join' | '} ,'-----'*$w'*$w*($_-ne$h)-join'-+-'} - I've adapted my answer from the topic Generate the shortest De Bruijn for the case
{String:'A'..'Z', n:2}. - The script loop by this sequence twice: each tail take two chars by row and by column
- The shortest De Bruijn sequence contains 676 chars. That's enough for 255 rows and for 255 columns
- The script add
random 9to row numbers to comply with the random requirement - The last line fixed. Output contains extra trailing newline
No-duplicate test generates #### strings instead ASCII tails and is looking for duplicates.