Generate random matrix with every number 0..k
You want to generate a random n*m matrix of integers 1..k with every integer used, and no integer used twice in any row.  And you want to do it efficiently.
If you just want to generate a reasonable answer, reasonably quickly, you can generate the rows by taking a random selection of elements, and putting them into a random order.  numpy.random.random_sample and numpy.random.shuffle can do that.  You will avoid the duplicate element issue.  If you fail to use all of your elements, then what you can do is randomly "evolve" this towards a correct solution,  At every step identify all elements that are repeated more than once in the matrix, randomly select one, and convert it to an as yet unused integer from 1..k.  This will not cause duplications within rows, and will in at most k steps give you a matrix of the desired form.
Odds are that this is a good enough answer for what you want, and is what you should do.  But it is imperfect - matrices of this form do not all happen with exactly equal probability.  (In particular ones with lots of elements only appearing once show up slightly more than they should.)  If you need a perfectly even distribution, then you're going to have to do a lot more work.
To get there you need a bit of theory.  If you have that theory, then you can understand the answer as, "Do a dynamic programming solution forwards to find a count of all possible solutions, then run that backwards making random decisions to identify a random solution."  Odds are that you don't have that theory.
I'm not going to give a detailed explanation of that theory.  I'll just outline what you do.
You start with the trivial statement, "There are n!/(n-m)! ways in which I could have a matrix with 1 row satisfying my condition using m of the k integers, and none which use more."
For i from 1..n, for j from m to k, you figure out the count of ways in which you could build i rows using j of the k integers.  You ALSO keep track of how many of those ways came from which previous values for j for the previous row.  (You'll need that later.)  This step can be done in a double loop.
Note that the value in the table you just generated for j=k and i=n is the number of matrices that satisfy all of your conditions.  We'll build a random one from the bottom up.
First you generate a random row for the last row of your matrix - all are equally likely.
For each row until you get to the top, you use the table you built to randomly decide how many of the elements that you used in the last row you generated will never be used again.  Randomly decide which those elements will be.  Generate a random row from the integers that you are still using.
When you get to the top you'll have chosen a random matrix meeting your description, with no biases in how it was generated.
Given an integer k, I am looking for a pythonic way to generate a nxm matrix (or nested list) which has every integer from 0..k-1 but no integer appears more than once in each row.
Currently I'm doing something like this
random.sample(list(combinations(xrange(k), m)), n)
but this does not guarantee every number from 0..k-1 is included, only that no integer appears more than once in each row. Also this has combinatorial complexity which is obviously undesirable.
Thanks.