This isn't a complete answer, but it might shed some light on what is involved.

Let $n=m(m-1)/2$, and let's say you've decided which pairs of the $m$ points should get which of the $n$ distances. You should form the $m\times m$ matrix $M$ whose entries are the squared distances, i. e., $M\_{ij}=||x\_i-x\_j||^2$, where the $m$ (unknown) points are $x\_1,\ldots,x\_m$. Suppose the $m$ points all belong to $\mathbb{R}^k$. Let $X$ be the $k\times m$ matrix whose $j$-th column is $x\_j$. Without loss of generality, the points have mean zero, so $x\_1 + \ldots + x\_m = X\alpha^T = 0$, where $\alpha=(1,\ldots,1)$. It's easy to show that if $P=I-\frac1m\alpha \alpha^T$ is the orthogonal projection onto the orthogonal complement of $\alpha$, then $PMP = -2X^TX$. Thus, once you know $M$, you can attempt to find $X$ by a modification of Cholesky decomposition applied to $-\frac12PMP$. You need to modify the procedure to make it return a $k\times m$ matrix, not an $m\times m$ matrix. (Since you want $\mathbb{R}^3$, you should take $k=3$.) If it succeeds, then you have a solution; otherwise, no solution exists.

Unfortunately, that assumes that you've assigned the $n$ distances to pairs of points already. If the above procedure fails, then it's still completely possible that some other assignment of distances to pairs will yield a solution. I'm not seeing any easy way to solve this; checking all possible assignments is out of the question even for pretty modest values of $m$ even if you can break all the symmetries, since I think you would need to check $(m(m-1)/2)!/m!$ assignments in the worst case. Maybe there's a way to reduce the number of permutations you need to check, but I'm not seeing it.