Assuming you can live with an approximate solution: you can re-formulate the problem as a graph embedding (or metric embedding) problem.
Your $N$ atoms $a_1,\dots,a_N$ are the vertices (nodes) of a graph $G$.
For every pair of atoms $(a_i, a_j)$ for which you know a distance, you create an edge (link) in $G$. Now assign a length to each edge, using the known distance $d(a_i,a_j)$. Note that the edges in this graph will have nothing to do with the atomic bonds in your molecule, they are just there to capture the known distances.
Your task is to find an embedding $f: G \rightarrow R^3$ of the graph into the 3-dimensional space $R^3$, such that $dist(f(a_i), f(a_j))=d(a_i, a_j)$, where $dist$ is the actual euclidean distance in $R^3$.
One way to do that is to model the edges as springs, with lengths $d(a_i, a_j)$ and simulate the resulting mechanical system. Start with arbitrary positions of the atoms. At each time step compute the resulting force from all the springs that are attached to an atom. Move a little into that direction. Repeat. The system will come to rest at or near a solution of your problem (ignoring oscillations and such). Stopping criteria for the simulation might be: it (nearly) stops moving, total energy has reached a minimum, distances are close enough to the desired $d(a_i, a_j)$ etc.
Check out Force directed graph drawing, or just use some physics engine to simulate the whole thing. There is a bunch of literature about these kinds of simulations, how to optimize them, how to avoid getting stuck in local minima etc.
Regarding exact solutions, I'd suspect that you cannot get a closed-form solution, i.e. some formula that takes the $d(a_i, a_j)$ as input and produces valid positions of the atoms as outputs. Same for getting all the atom distances as outputs.