A natural way to approach this question is to ask for an eigenform $f$ with coefficients in a local field $K$ with residue field degree $\ge 2$. Or, asking for slightly more, with coefficient ring $\mathcal{O}$ admitting a surjective map to a field $\mathbf{F}$ of order divisible by $4$ (this is slighly more since the rings $\mathcal{O}$ can typically be non-trivial orders in $\mathcal{O}_K$). By Serre's conjecture, this is equivalent to asking for the existence of an irreducible Galois representation
$$\rho: \mathrm{Gal}(\overline{\mathbf{Q}}/\mathbf{Q}) \rightarrow \mathrm{GL}_2(\mathbf{F})$$
with Serre weight and conductor $(2,p)$ (note, no oddness condition!). It's hard to construct such representations, but one natural way is to use induced ($=$ projectively dihedral) representations.
If $E$ is the corresponding quadratic extension, and $F/E$ the cyclic extension, then the Serre weight and level will be $(2,p)$ providing that $F/E$ is totally unramified and $E = \mathbf{Q}(\sqrt{-1})$, $\mathbf{Q}(\sqrt{p})$, or $\mathbf{Q}(\sqrt{-p})$.
(EDIT: In a previous version of this post, I only thought about extensions that were totally unramified at $2$ for some unknown reason.)
One is in good shape providing that the odd part of the class group of one of the fields $\mathbf{Q}(\sqrt{\pm p})$ is not $(\mathbf{Z}/3 \mathbf{Z})^n$. Since one can't really say much about real quadratic fields, let's think about the imaginary quadratic fields.
It's a theorem, proved by (amongst other people) Lillian Pierce, and Jordan Ellenberg and Akshay Venketesh, that
the 3-torsion part of the class group is a negligible part of the class group. Thus we are done if $p$ is big providing that the $2$-part of the class group is not so big. The $2$-part is trivial if $p$ is $3$ mod $4$, and has order $2$ if $p$ is $5$ mod $8$. However, it is quite possible that the class group of $\mathbf{Q}(\sqrt{-p})$ is $\mathbf{Z}/2^n \mathbf{Z}$, and very rough heuristics suggest that this might happen infinitely often.
[EDIT: LaTeX issues now mostly sorted in the sequel]
If $\mathbf{T}$ denotes the Hecke algebra tensored with $\mathbf{Z}_2$, then
$\mathbf{T}$ is a free $\mathbf{Z}_2$-module of rank $n = \mathrm{dim}(S_2(\Gamma_0(p)))$.
It is also a semi-local ring. For each maximal ideal $m$ of $\mathbf{T}$, we are asking that
$$\mathbf{T}_{m} \otimes \mathbf{Q}$$
is not a number of copies of the 2-adic numbers. If $m$ is the $2$-adic Eisenstein ideal, then in a paper with Matthew Emerton, I prove that
$$\mathbf{T}_{m}/2$$
has rank $2^{e-1}-1$, where the $2$-part of the class group of
$\mathbf{Q}(\sqrt{-p})$ (we may assume that $p$ is $1$ modulo $8$) has order $2^{e}$.
If $p$ is $9$ modulo $16$ then $\mathbf{T}$ localized at $m$ is also a domain, and so we are done in this case if $2^{e-1} -1 \ge d$. Even if $p$ is $1$ modulo $16$, this shows that the bulk of $\mathbf{T}/2$ must come from non-Eisenstein primes $m$, since
$2^e \le h \ll p^{1/2 + \epsilon} \ll p/12 \simeq n$.
So, in the case $d = 1$, one may assume that the odd part of the class group is
$3$-torsion, and then hope that for the corresponding $m$, one can prove that
the corresponding rings $\mathbf{T}_{m}/2$ can't be too large.
It turns out that the relevant question becomes: Given a $\overline{\rho}$ corresponding to an $S_3$ extension, and given a finite flat deformation of
$\overline{\rho}$ to $\mathrm{SL}_2(A)$ for a local ring $A$ killed by $2$, can one bound the rank of $A$ as an $\mathbf{F}_2$-module? For example, can one prove that $A$ has rank $p^{1 - \epsilon}$? The example of Eisenstein $m$ suggests that one can not neccesarily do better than $p^{1/2 + \epsilon}$.
Here is an answer that shows works for d = 1, and works for general d assuming GRH.
Step I. Let $C$ be the class group of $\mathbf{Q}(\sqrt{-p})$. The group $C$ decomposes as
$C_{odd} \oplus C_{even}$.
Step II. Suppose that $C_{odd}$ is not annihilated by $2^{2d} - 1$. Then there exists a dihedral representation induced from a character of $C_{odd}$ which is finite flat at $2$, ordinary at $p$, and has which has image in
$$\mathrm{SL}_2(\mathbf{F})$$
for a field $\mathbf{F}$ of degree $>d$.
Thus we are done unless $C_{odd} = C_{odd}[2^{2d} - 1]$.
Step III. If $d = 1$, then then the $2^{2d} - 1 = 3$-torsion of $C_{odd}$ has small order, namely, of order at most
$$p^{1/2 - \delta}$$
for some explicit $\delta > 0$. For general $d$, the $2^{2d} -1$-torsion has order at most $p^{\epsilon}$, assuming GRH.
Step IV: If $p$ is $-1$ modulo $4$ or $5$ modulo $8$, then $C_{even}$ has order $\le 2$.
This implies by Steps II and III that $C$ has order $\le p^{1/2 - \delta}$, which contradicts the estimate $h \gg p^{1/2 - \epsilon}$.
Step V: We may assume that $p$ is $1$ modulo $8$. Let $|C_{even}| = 2m$. Using the estimate $h \gg p^{1/2 - \epsilon}$, we deduce that
$m \gg p^{\delta - \epsilon}$ for some explicit $\delta > 0$.
Step VI: Let $\mathbf{T}$ denote the localization of the Hecke algebra at the Eisenstein prime of residual characteristic $2$. It is a consequence of one of the main theorems of FC-ME that one has $\mathbf{T} = \mathbf{Z}_2[x]/f(x)$, where:
$$f(x) \equiv x^{m - 1} \ \mathrm{mod} \ 2,$$
$$\mathbf{Z}_2/f(0) \mathbf{Z}_2 \simeq \mathbf{Z}_2/n \mathbf{Z}_2,$$
and $n$ is the numerator of $(p-1)/12$. (Compare the discussion in Mazur's Eisenstein ideal paper, section 19, page 140.)
Step VII: If the coefficients of all forms of level $\Gamma_0(p)$ define extensions of degree $\le d$, then the normalized $2$-adic valuation of every root of $f(x)$ is at least $1/d$. We deduce that
$$\frac{m - 1}{d} \le v_2(n),$$
Since $v_2(n) \le \log_2(n) < \log_2(p)$, we deduce that
$$ m \le d \log_2(p).$$
This contradicts the previous estimate $m \gg p^{\delta - \epsilon}$ for sufficiently large $p$.
Remark: For $d = 1$, it should be easy to use the unconditional results to give an explicit lower bound on possible $p$.
To summarize, for any $d$, and sufficiently large $p$, there exists either:
(i) A modular form $f$ of level $\Gamma_0(p)$ with coefficients in an extension of $\mathbf{Q}_2$ which contains an unramified extension of degree $> d$, and whose residual representation is dihedral,
(ii) A modular form $f$ of level $\Gamma_0(p)$ which coefficients in an extension of $\mathbf{Q}_2$ which contains a ramified extension of degree $> d$, and whose residual representation is Eisenstein.
Extra: For any $p$, the coefficients of an $f$ of level sufficiently divisible by $p$ contains the totally real subfield of the $p^n$th roots of unity.
For any $p$, and sufficiently large $n$, this contains a large extension of the $2$-adic numbers.
Reason why this argument still sucks: Doesn't work at all for primes $> 2$, and uses GRH for $d > 1$.
