This is an experimental way of working out the inverse.
We can treat the polynomial like an expansion
\begin{equation}
f(x) = -1 + x + 0x^2 + 2x^3 + 0x^4 + x^5 + 0x^6 + 0x^7 + \cdots
\end{equation}
then we can perform a Series Reversion on this to give the inverse series (as an infinite expansion) \begin{equation}
f^{-1}(x) = (1+x) -2(1+x)^3 +11(1+x)^5-80(1+x)^7+665(1+x)^9-\cdots
\end{equation}
at a glance this doesn't seem to helpful, but if we search the coefficients in the OEIS we seem to get a hit! It would appear (conjecture) that the general coefficient is then \begin{equation}
a(n) = \binom{5n+1}{n}\frac{(-1)^n}{2n+1}
\end{equation}
and we could write that \begin{equation}
f^{-1}(x) = \sum_{n=0}^\infty \binom{5n+1}{n}\frac{(-1)^n}{2n+1}(x+1)^{2n+1}
\end{equation}
if we evaluate that in Mathematica, it gives \begin{equation}
f^{-1}(x)=(1+x)\;_4F_3\left(\frac{2}{5},\frac{3}{5},\frac{4}{5},\frac{6}{5}\bigg|\frac{3}{4},\frac{5}{4},\frac{6}{4}\bigg|-\frac{5^5}{4^4}(1+x)^2 \right)
\end{equation}
a generalised hypergeometric function. If we plot the composition of these two i.e $f(f^{-1}(x))$ or $f^{-1}(f(x))$ the plot seems to indicate \begin{equation}
f(f^{-1}(x))=f^{-1}(f(x))=x
\end{equation}
of course this is not a proof, and evaluating the inverse function may become numerically unstable if $x$ becomes too large.
As you point out, $h^{-1}$ maps naturals to pairs $(m, n)$. If you think about what $h^{-1}$ is doing, you'll see that you need to find a pair $(m, n)$, $m \in \mathbb{N}_0$, $n \in \mathbb{N}$ such that $m+n$ is the function $h^{-1}$'s input. That is, if $h^{-1}(k) = (m, n)$, then $m + n = k$. An easy approach is to fix some $m$ first, then let $n = k - m$. This will work provided $k > m$. We can then handle the remaning cases separately. This gives $h^{-1}(n) = (0, n)$ as a simple example, since $(0, n) \in \mathbb{N}_0 \times \mathbb{N}$. So that gives one right inverse. Another can be given by, for example,
$$h^{-1}(n) = \begin{cases}(1, n-1), & \mbox{if } n > 1\\(0, 1), & \mbox{if } n = 1\end{cases}$$
Can you devise a suitable function for $m = 2$? For $m = 3$?
Best Answer
This function probably won't have a nice inverse, since finding the inverse is equivalent to solving the equation $f(x)=c$, or equivalently finding the roots of the equation $x^5+x^3+x-c=0$. This is a quintic polynomial, and as such probably will likely not have a general solution (i.e. for all $c$) in terms of radicals. The best you can do is usually some kind of numerical method.