It is true that one can always find an $m$-sparse solution.

If $\hat x$ is solution and $\|\hat x\|_0 \ge m+1$, one can perform a small gradient step (with respect to the L1 norm) in a neighborhood of $\hat x$ restricted to vectors that have the same support and the same signs.

Let $X=\{x: \hat x_i =0\Rightarrow x_i=0, \hat x_i \ne 0 \Rightarrow \hat x_i x_i \ge 0 \}$ (same support and same signs as $\hat x$, and let $W=\{ x: Ax =b\}$ and $V = \{x: \hat x_i = 0 \Rightarrow x_i = 0\}$.
The subspace $V \cap W$ has dimension at least $m+1 + (N-m) - N \ge 1$ hence $V \cap W$ contains at least a line.
In $X\cap W \cap V$ the L1 norm is simply $\sum_j x_j s_j$ where $s_j=sign(\hat x_j)$ and we can move in the direction of the gradient of the L1 norm while staying in $X\cap V \cap W$.

Two things may happen as we move in this gradient descent direction: either we reach the boundary of $X\cap W \cap V$, or we stay indefinitely in $X$ and move towards $\infty$. The latter is not possible because moving in the gradient descent direction decreases the L1 norm. Hence we must reach the boundary of $X\cap W \cap V$.

When we reach the boundary of $X\cap W \cap V$ in this gradient direction, we have not increased the L1 norm (that's the point of the gradient descent direction), we are still in the space $W=\{x: Ax=b\}$, and reaching the boundary of $X$ means that one coordinate becomes 0 so we have decreased the sparsity of the solution by at least 1.