Multidimensional scaling (MDS) is one algorithm that tries to find such a set of points. It's usually used for visualization, so it's usually used in 2 or 3D spaces, but the optimization procedure itself can be used in arbitrary dimensions.
To get random samples, you can initialize with random vectors before optimizing, though it is not clear what distribution you'd be sampling from in this case.
EDITED: Sample MATLAB code to generate $P$ patterns of size $N$ with the same distances as a reference data:
data=mdscale(pdist(reference_data), N, 'Start', 'Random');
or using an Euclidean distances matrix
D of size $P\times P$:
data=mdscale(D, N, 'Start', 'Random');