x = [1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20];
EDIT after Mohammad's coment
[m,n] = size(x);
df = bsxfun(@plus,fullfact(m*ones(1,n)),(0:n-1)*m);
k = randperm(size(df,1));
out = x(df(k(1:min(100,numel(k))),:));
OR
[m,n] = size(x);
xc = mat2cell(x,m,ones(n,1));
cc = cell(1,n);
[cc{:}] = ndgrid(xc{:});
k = randperm(numel(cc{1}));
out = cell2mat(cellfun(@(x)x(k(1:min(100,numel(k)))'),cc,'un',0));
