A non-linear molecule has $3N-6$ degrees of freedom ($N$ is the number of atoms; ignoring translation and rotation). Therefore, a set of $3N-6$ distances and/or angles is enough, to describe the whole system.
I am searching for an algorithm, which takes $3N-6$ ($N$ is the number of points) distances as an input and calculates all ${{N(N-1)/2}}$ distances between all points.
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.
Similar to Berth's suggestion, you could fix one atom and try to minimize the function $$g(f)=\sum_{(i,j)\in G}\left[d(f_i,f_j)^2 -d_{ij}^2\right]^2$$ where $f$ is a matrix of 3D coords. This function is non-convex and should be optimized using a global optimization technique.
