This may or may not be what you're looking for, but I thought the idea was fun, so I'll share:
This will be a non-symmetric metric on $\mathbb{Z}^+$:
Suppose that one is only allowed to move left one unit, and in addition, one is allowed to jump right from one power of two to the next. I.e., to find a sequence of steps to get from 5 to 11, one must travel as follows:
$ 5 \to 4 \to8 \to16 \to15 \to 14 \to13 \to12\to11. $
For a (positive) integer $n$, define $T(n)$ to be largest power of $2$ which is less than or equal to n. Similarly, define $S(n)$ to be the smallest power of $2$ greater than or equal to $n$. Then, if $|\cdot|$ denotes the usual absolute value, we have:
$ d(x,y) = \left\{ \begin{array}{lcc} |x - y| & & x \geq y \\ |x - T(x)| + \log_2(S(y)/T(x)) + |S(y) - y| & & x < y \end{array} \right. $
If $x \leq y$, one just moves left $|y - x|$ units. If not, one moves from $x$ to the largest power of $x$ less than or equal to $x$. One then jumps $\log_2(S(y)) - \log_2(T(x))$ powers of $2$, and finally moves the remaining $|S(y) - y|$ units. It is not hard to show that this a metric (It clear satisfies condition (i), and to show it satisfies (ii), one just needs to consider the case of $d(x,y)$ when x > y).
This metric came to mind in lieu of Cauchy's Proof of the Arithmetic-Geometric mean inequality (http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means#Proof_by_Cauchy).
Let $P(n)$ denote the statement that the AG-mean inequality is true for $n$ numbers. Cauchy's idea was to prove the inequality by first inducting along powers of two (i.e., P($2^k$) is true implies P($2^{k+1}$) is true. Then, he showed that $P(n)$ is true implies $P(n-1)$ is true.
Assuming that we know the arithmetic-geometric mean inequality is true for some step $n$, $d(n,m)$ is the number of steps needed using Cauchy's proof to show $P(m)$ is true, assuming that we know $P(n)$ is true.