Let $c\colon[n]\times[n]\to\mathbb R$ be any (say transportation cost) function, which may or may not be a metric; here $[n]:=\{1,\dots,n\}$. Then what you apparently want is the Kantorovich--Rubinstein--Wasserstein distance corresponding to the transportation cost function $c$, defined by the formula $$d(x,y):=\min\Big\{\sum_{i,j=1}^n c(i,j)m_{i,j}\,\colon m\in M_{x,y}\Big\}$$ for all $x=(x_1,\dots,x_n)$ and $y=(y_1,\dots,y_n)$ in $\mathbb{R}_+^n$, where $M_{x,y}$ is the set of all $n\times n$ matrices $m$ with nonnegative real entries $m_{i,j}$ such that $$\sum_{j=1}^n m_{i,j}=x_i\quad\text{and}\quad \sum_{i=1}^n m_{i,j}=y_j$$ for all $i$ and $j$ in $[n]$.
For instance, here is Mathematica's calculation of the ($\ell^1$-)optimal transportation plan for your Example 4) -- which gives the same result, $1/2$, as yours:
We see that it takes Mathematica about 0.014 sec to compute this optimal plan.