These kinds of inverse relations are equivalent to orthogonal relations between sets of numbers.
Suppose you have two triangular sets of numbers $a_{n,k}$ and $b_{n,k}$, each defined for $k = 0, 1, \ldots, n$, such that $$\sum_{k=m}^n b_{n,k} a_{k,m} = \delta_{nm}.$$ Then $a_{n,k}$ and $b_{n,k}$ are orthogonal, and they have the inverse property you are asking for in (3); i.e., if $f_n = \sum_{k=0}^n a_{n,k} g_k$ then $g_n = \sum_{k=0}^n b_{n,k} f_k$, and vice versa.
Proof: $$\sum_{k=0}^n b_{n,k} f_k = \sum_{k=0}^n b_{n,k} \sum_{m=0}^k a_{k,m} g_m = \sum_{m=0}^n \left(\sum_{k=m}^n b_{n,k} a_{k,m}\right) g_m = g_n.$$
Thus binomial inversion follows from the "beautiful identity" $$\sum_{k=m}^n (-1)^{k+m} \binom{n}{k} \binom{k}{m} = \delta_{nm}.$$
Since the orthogonal relation and the inverse relation are equivalent, perhaps the proof of this identity given by Aryabhata or the proof by Yuval Filmus can be considered a combinatorial proof of the inverse relation you describe for binomial coefficients.
Other examples
The Lah numbers $L(n,k)$ satisfy $$\sum_{k=m}^n (-1)^{k+m} L(n,k) L(k,m) = \delta_{nm},$$ and so, like the binomial coefficients, are (up to sign) self-orthogonal and have the inverse relation
$$f_n = \sum_{k=0}^n L(n,k) g_k \Leftrightarrow g_n = \sum_{k=0}^n (-1)^{k+n} L(n,k) f_k.$$
The two kinds of Stirling numbers, $\left[ n \atop k \right]$ and $\left\{ n \atop k \right\}$, are orthogonal, satisfying
$$\sum_{k=m}^n (-1)^{k+m} \left[ n \atop k \right] \left\{ k \atop m \right\} = \delta_{nm}$$
and
$$\sum_{k=m}^n (-1)^{k+m} \left\{ n \atop k \right\} \left[ k \atop m \right] = \delta_{nm}.$$
Thus they satisfy the inverse relation
$$f_n = \sum_{k=0}^n \left[ n \atop k \right] g_k \Leftrightarrow g_n = \sum_{k=0}^n (-1)^{k+n} \left\{ n \atop k \right\} f_k.$$
John Riordan wrote a paper "Inverse Relations and Combinatorial Identities" (American Mathematical Monthly 71 (5), May 1964, pp. 485--498) and devoted two of the six chapters of his text Combinatorial Identities to these kinds of inverse relations. For example, he shows how inverse relations can be derived from Chebyshev polynomials (since they are orthogonal) and Legendre polynomials (since they are also orthogonal). See the article or the book for many more examples.
Additional comments and consequences
The proof using the orthogonal relation can also be applied with respect to the upper index to obtain inverse relations based on the upper index rather than the lower. Thus, for example, we also have (provided, of course, that the sums converge) $$f_n = \sum_{k=n}^\infty \binom{k}{n} g_k \Leftrightarrow g_n = \sum_{k=n}^\infty (-1)^{k+n} \binom{k}{n} f_k,$$
as well as the same kind of thing for the Lah numbers, Stirling numbers, and the other examples.
In addition, these orthogonal relations mean that matrices consisting of orthogonal numbers are inverses. Thus, for example, if $A$ and $B$ are $n \times n$ matrices such that $A_{ij} = \binom{i}{j}$ and $B_{ij} = (-1)^{i+j} \binom{i}{j}$ then the orthogonal relationship implies that $AB = I$. This, of course, means that $BA = I$ as well, and so every orthogonal relationship goes both ways; i.e., $$\sum_{k=m}^n b_{n,k} a_{k,m} = \delta_{nm} \Leftrightarrow \sum_{k=m}^n a_{n,k} b_{k,m} = \delta_{nm}.$$
For more on inverse matrices consisting of combinatorial numbers, see my answer to the question "Stirling numbers and inverse matrices."
Let $$f_n(z)=\sum_{q=0}^\infty \binom {n+q-1}q z^q$$
Claim: This is $(1-z)^{-n}$.
Then $f_n(z)f_m(z) = f_{n+m}(z)$. But the left hand side of your formula is the coefficient of $z^N$ in $f_n(z)f_m(z)$, and the right hand side is the coefficient of $f_{n+m}(z)$.
The proof of the claim is the generalized binomial expansion, and uses the fact that $$\binom {-n} q = (-1)^q \binom {n+q-1}{q}$$
Alternatively, you can rewrite your statement as:
$$\sum_{q=0}^N \binom {-m} q \binom {-n}{N-q} = \binom {-(m+n)}q$$
Best Answer
$\binom{n+k-1}{k}$ is the number of ways to place $k$ indistinguishable balls into $n$ boxes. Consider $k$ stars \begin{eqnarray*} \underbrace{** \cdots *}_{ k \text{ stars}} \end{eqnarray*} insert $n-1$ bars to form $n$ boxes \begin{eqnarray*} \underbrace{** }_{ k_1 \text{ stars}} \mid \underbrace{*** }_{ k_2 \text{ stars}} \mid \cdots \mid \underbrace{*}_{ k_n \text{ stars}} \\ \sum_{i=1}^{n} k_i=k. \end{eqnarray*} This is the same as picking the terms from \begin{eqnarray*} (1+x+\cdots+x^{k_1}+\cdots) (1+x+\cdots+x^{k_2}+\cdots) \cdots (1+x+\cdots+x^{k_n}+\cdots) \end{eqnarray*} So \begin{eqnarray*} \frac{1}{(1-x)^n} =\sum_{k=0}^{\infty} \binom{n+k-1}{k} x^k . \end{eqnarray*}