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.


* * *

We can be a little more explicit. Let $h\in V\cap W \setminus \{ 0 \}$ (which always exists because $V\cap W$ contains a line)
and by changing $h$ to $-h$ if necessary, assume that $\sum_j h_j s_j \ge 0$. As long as $t>0$ is small enough so that $x^t = \hat x - t h$ is in $X$, we have
$$
\|x^t \|_1 = \sum_j s_j (\hat x_j - t h_j) = \|\hat x\|_1 - t \sum_j s_j h_j.
$$
A solution with sparsity at most $\|\hat x\|_0 - 1$ nonzero coordinates is $x^{t_0}$ for $t_0=\inf \{t>0: s_j(\hat x_j - t h_j) > 0\}$.