An explicit bound on $M$ can be proved. It is not clear to me if the modularity of $\rho$ would help improve such bounds. One can use the best available numerical bounds on the least norm of an unramified prime ideal with a given Artin symbol. For the Galois extension inherent in your setting, the best such unconditional results are due to Thorner and Zaman. One can do much better under assumptions like the strong Artin conjecture and the generalized Riemann hypothesis.
To give an example of what sort of bound you might expect to achieve (as a function of $N$ and $\ell$), it follows from Theorem 1.5 in Thorner-Zaman that for $f=\sum_{n=1}^{\infty}a_f(n)q^n\in\mathbb{Z}[[q]]$ satisfying your hypotheses (and also having trivial nebentypus), the following result holds: There exists an absolute constant $c>0$ such that for all $a\in\mathbb{Z}$, there exists a prime $p\nmid N\ell$ such $a_f(p)\equiv a\pmod{\ell}$ and $p\leq c \ell^{4515+695\omega(N)}\mathrm{rad}(N)^{1736\ell+1042}$. (Here, $\omega(N)$ is the number of distinct prime divisors of $N$, and $\mathrm{rad}(N)$ is the product of the distinct prime divisors of $N$.)
So for your question, if $\ell$ is fixed and $N$ is large, expect polynomial dependence on $N$. If $N$ is fixed and $\ell$ is large, expect super-polynomial dependence on $\ell$. Under GRH, you can expect a bound that is polynomial in $\ell$ and polynomial in $\log N$, perhaps of the form $O(\ell^4 (\log(\ell N))^2)$. This conditional bound can be made completely explicit (see, for example, the conditional explicit bounds on the least unramified prime ideal in the CDT by Bach and Sorenson) for the purposes of checking results with a computer. The unconditional result seems to be too unwieldy for such purposes.
