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).  In this embedding, all of the $N$ points are at the vertices of the $N$-dimenional **unit hypercube**.  In the unit hypercube embedding, the Hamming distance is between each pair of points is $2$, and the Minkowski distance between each pair of points if $\sqrt(2)$


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 each pair of points.  Of course, if the distances are not in a Euclidean space, you can't use a Minkowski metric to define the distances.  

If you want to have this be a euclidean space, then you can use different techniques to get the appropriate desired pair-wise Minkowski metric distance, 

$$d_{a,b}={(\sum_{i=1}^{i=N}} (a_i-b_i)^2) ^{0.5}$$ 

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.

Thus now you would have each point $P_n, 1\le n \le N$ at $(v_1,v_2,...,v_N)$ where $v_i=0$ for $i \ne n$, and $v_i=d_i$ for $i=n$.  This embedding now places each of the points at a vertex of a **hyper-rectangle** in $N$-dimensional space, rather than in the unit hypercube.

You could use an annealing method or a genetic algorithm with multiple candidates to mutate and 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$?