You more or less have it.

I haven't a clue how I'd go about it though :( (Offers?:)

For my standard consulting rate? ;-)

Basically, you want to take a uniform distribution between 0 and M, and map it to a non-uniform one between 0 and N, so that X+I < X+J when I < J. One way to do this is to generate a step-functionpiecewise linear function, then translate values through that step function. In Matlab, it looks something like this for a 10-step function:

fx = [0,cumsum(unifrnd(0,1,1,10))];
tmp=unifrnd(1,10,1,1e5);
ix=floor(tmp);
dx=rem(tmp,1);
values = (fx(ix) + (fx(ix+1)-fx(ix)).*dx)./fx(end-1);
[download]

Using a spline would be more complicated, but would be smoother.