No. It is not true. The theorem you state "assumes" the existence and uniqueness of the solution and proves that in this case, you this particular solution cannot have more non-zero components than the number of measurements. The existence is proven under RIP (Chapter 6, e.g. Theorems 6.9 and 6.15), null space properties (Chapter 4, e.g. Theorem 4.4), incoherence properties (Chapter 5, e.g. Theorem 5.16), ... and I think that's it as of today.

Good luck with this beautiful field!

No. It is not true. The theorem you state "assumes" the existence and uniqueness of the solution and proves that in this case, you this particular solution cannot have more non-zero components than the number of measurements. The existence is proven under RIP (Chapter 6, e.g. Theorems 6.9 and 6.15), null space properties (Chapter 4, e.g. Theorem 4.4), incoherence properties (Chapter 5, e.g. Theorem 5.16), ... and I think that's it as of today.

EDIT: As suggested in a comment here is a counter example:

Consider the case where $N = 2$, $m = 1$ and take $A = [1,1] \in \mathbb{R}^{1 \times 2}$. Your optimization problem becomes, take $b \in \mathbb{R}^m$ as you wish, say $3$ $$\min \|(x,y)\|_1 \quad s.t. \;\; x+y = 3,$$

In this case, you have infinitely many solutions $\{(x,y): x = 3-y, 0 \leq y \leq 3 \}$. They all have a $\ell^1$ norm equal to $3$ and yet only $2$ of them are $1$-sparse.