Perhaps I'm not following what you're asking perfectly, but if you have $N$ points, and a distance matrix which is $N \times N$ in size, you could use an $N$-dimensional hypercube.
This hypercube would have the $N$ points at the $N$ vertices defined by the vectors $P_1=(1,0,...,0)$, $P_2=(0,1,0,...,0)$, ..., $P_N=(0,0,...,0,1)$. Thus the $N$ points all exist at Hamming distance $=1$ from the origin (0,0,...,0). The pair-wise distances which you already have as a given are used to define the length of the distance between two vertices and thus give the separation between the hyperplanes defined for each point.
Of course, if the distances are not in a Euclidean space, you can't use a Minkowski metric to define the distances. Then you can set each point to be at a distance $d_n, 1<\le n \le N$, then calculate the pairwise distances for all of the data points and try to move the points around in order to get closer to approximating your original distance metric.
You could use a genetic algorithm with multiple candidates to cross over, or try to move one point at a time to optimize that point's pair-wise distance to all of the other points.
What is the order of magnitude of your data set's $N$?