Here's a brute force construction that I think works. If not, then, well, it's at least a start. I'll try to be as precise as possible. Here is the statement I would like to prove.
Let $n\geq 2$ be an integer, and let $\sigma_{ij}$ for $i,j\in \{1,\ldots, n\}$ be real numbers as given in the problem. Let $\alpha_1,\ldots, \alpha_n$ be any distinct points in $\mathbb{R}^3$. Then there is a continuous $W\colon \mathbb{R}^3\to \mathbb{R}_{\geq 0}$ which vanishes precisely at the $\alpha_i$ such that $d_W(\alpha_i,\alpha_j) = \sigma_{ij}$, where $d_W$ is the distance induced by $W$ as described in the problem.
It is easy to see that if you could prove this, then it holds in $\mathbb{R}^m$ for all $m\geq 3$, just by embedding $\mathbb{R}^3\subseteq\mathbb{R}^m$. The case of $\mathbb{R}^2$ seems a little trickier, and I will talk about it later.
Lemma 1. Suppose that $\alpha_1,\ldots, \alpha_n\in \mathbb{R}^3$ are distinct points such that there is an $W$ solving the problem for the $\alpha_i$. Let $\beta_1,\ldots, \beta_n\in \mathbb{R}^3$ be any other distinct points. Then there is a $W'$ solving the problem for the $\beta_i$.
Proof: Let $h\colon \mathbb{R}^3\to \mathbb{R}^3$ be a homeomorphism mapping $\beta_i$ to $\alpha_i$. To get $W'$ you need only pull back the metric induced by $W$ via $h$.
Thanks to this lemma, it suffices to prove the existence of $W$ for any (convenient) set of points $\alpha_1,\ldots, \alpha_n\in \mathbb{R}^3$. I will choose $\alpha_1,\ldots,\alpha_n$ as follows.
Assumption. Let $L_{ij}$ denote the straight line segment connecting $\alpha_i$ and $\alpha_j$. We assume $\alpha_1,\ldots,\alpha_n$ are such that two distinct $L_{ij}$ can only intersect at their endpoints. Moreover, we assume that $\|\alpha_i - \alpha_j\|\ll\sigma_{ij}$.
This assumption very much uses the fact that we are in $\mathbb{R}^3$; it would not work in $\mathbb{R}^2$.
I will use the following notation.
- $B_i$ will denote the open Euclidean ball around $\alpha_i$ of radius $\delta>0$, where $\delta$ is small compared to the Euclidean distances between the $\alpha_i$, say $\delta = 10^{-8}\min_{i\neq j}\|\alpha_i - \alpha_j\|$.
- $T_{ij}$ will denote the open set $\{x\in \mathbb{R}^3 : d(x,L_{ij})<\varepsilon\}$, where $\varepsilon\ll\delta$ will be determined later.
- $M$ will denote a very large positive constant, to be determined later.
The function $W$ will be defined piecewise.
Step 1: For $x\in \mathbb{R}^3$ such that $x\notin \bigcup_i B_i\cup \bigcup_{ij} T_{ij}$, we define $W(x) = M$.
Step 2: Choose $\varepsilon$ to be small enough so that any two distinct $T_{ij}$ have intersection contained within one of the $B_i$. You can always do this by our assumption on the $\alpha_i$. We will next define $W$ on the set $\bigcup_{ij}T_{ij}\smallsetminus\bigcup_i B_i$. This set is a disjoint union of "cylinders" $T_{ij}\smallsetminus (B_i\cup B_j).$ For $x\in T_{ij}\smallsetminus (B_i\cup B_j)$, let $\pi_{ij}(x)$ denote the closest point on $L_{ij}$ to $x$. We begin by choosing a continuous "bump" function $f_{ij}\colon L_{ij}\to \mathbb{R}$ which $\geq 1$ everywhere, is $\equiv 1$ except in a small neighborhood of the midpoint of $L_{ij}$, and is $\equiv \Lambda_{ij}>1$ in a small neighborhood of the midpoint. Here $\Lambda_{ij}$ is a constant to be determined later, but we will always assume that $M\gg \Lambda_{ij}$ by adjusting $M$ if necessary. Define $W$ on $T_{ij}\smallsetminus B_i\cup B_j$ by $W(x) = M\frac{d(x,L_{ij})}{\varepsilon} + f_{ij}(\pi(x))\left(1 - \frac{d(x,L_{ij})}{\varepsilon}\right).$ Note that $W$ is radially symmetric in $T_{ij}\smallsetminus (B_i\cup B_j)$ around $L_{ij}$ and increasing with radius. It follows, in particular, that the line $L_{ij}$ is minimal geodesic for this $W$.
Step 3: It only remains to define $W$ in the balls $B_i$. Currently $W$ is defined and continuous on $\partial B_i$ for each $i$. We define $W$ in the $B_i$ by $B(x) = \frac{\|x - \alpha_i\|}{\delta}W\left(\alpha_{i} + \delta \frac{x - \alpha_i}{\|x - \alpha_i\|}\right).$ Note that the minimum value of $W$ in $\partial B_i$ is $1$, and this value is obtained exactly at the points $L_{ij}\cap \partial B_i$. It follows that the segments $L_{ij}\cap B_i$ are minimal geodesic segments for $W$ in $B_i$.
So now we have constructed $W$. It is continuous, it vanishes precisely at the $\alpha_i$, and we have show that the $L_{ij}$ are geodesics for $W$. Here's what this gives us:
Step 4: By adjusting the $\Lambda_{ij}$, we can make the length of $L_{ij}$ equal to $\sigma_{ij}$. We therefore get geodesic segments $L_{ij}$ from $\alpha_i$ to $\alpha_j$ of exactly the right length. Moreover, by making $M$ large enough, we can ensure that these geodesics are minimal: if $M$ is large enough, no minimal geodesic from $\alpha_i$ to $\alpha_j$ will pass through the region $\mathbb{R}^3\smallsetminus (\bigcup_k B_k\cup\bigcup_{k,l}T_{kl})$.
I think this construction, though a pain to write out, works for $\mathbb{R}^3$. In $\mathbb{R}^2$ it doesn't work since you cannot choose the $\alpha_i$ as in our assumption. In order to adapt this method to $\mathbb{R}^2$, something you can do would be to choose your $\alpha_i$, and consider the graph $\bigcup_{ij}L_{ij}$. Assign to each edge a weight such that $\alpha_i$ and $\alpha_j$ are at a distance $\sigma_{ij}$ apart with respect to these weights. You can then do the above procedure to construct a $W$ which makes each of the edges in the graph minimal geodesic with length equal to that weight.
I hope this all works. I'm curious to hear what people think.