$\newcommand\rhobar{\overline{\rho}}$
$\newcommand\Q{\mathbf{Q}}$
$\newcommand\GL{\mathrm{GL}}$
$\newcommand\F{\mathbf{F}}$
$\newcommand\Frob{\mathrm{Frob}}$
If $\rhobar: G_{\Q} \rightarrow \GL_2(\F) = \GL(V)$ is a (projectively) dihedral representation, then congruences between $\overline{\rho}$ and non-projectively dihedral forms are captured by $H^1_{\Sigma}(\mathbf{Q},W)$, where the adjoint representation of $V$ decomposes as $1 \oplus \chi \oplus W$, and the subscript $\Sigma$ denotes that we are considering the appropriate Selmer group. One can see this by noting that projectively dihedral deformations correspond to deforming the induced character, which (with fixed determinant) comes down to $H^1_{\Sigma}(\Q,\chi)$. The group $H^1_{\Sigma}(\Q,W)$ can certainly be non-zero, even in the minimal case. In your second problem, the assumption amounts to asking (in particular) that $H^1_{\emptyset}(\Q,W) = 0$. By the Greeberg-Wiles Euler characteristic formula, this certainly implies that the dual Selmer group also vanishes. If you now allow ramification at an auxiliary prime $\ell$, then the condition on the dual Selmer group becomes more restrictive, and hence it is still zero. Thus, by the Greeberg-Wiles formula again, we deduce that (with $\Sigma$ indicating no condition at $\ell$):
$$|H^1_{\Sigma}(\Q,W)| = \frac{|H^1(\Q_{\ell},W)|}{|H^0(\Q_{\ell},W)|} = |H^0(\Q_{\ell},W(1))|,$$
The second equality coming from local duality ($W$ is self dual, so its Cartier dual is $W(1)$). So you get new deformations whenever the group on the right is non-trivial. If $\rhobar(\Frob_{\ell})$ has eigenvalues $\alpha_v$ and $\beta_v$ then the eigenvalues of $W \oplus \chi$ are $\alpha_v/\beta_v$, $\beta_v/\alpha_v$, and $1$. So:
If $\chi(\Frob_{\ell}) = 1$, you get new deformations if the ratios of the eigenvalues in some order are $\ell$,
If $\chi(\Frob_{\ell}) = -1$, then $\rho(\Frob_{\ell})$ has projective order two, and so the eigenvalues of $W \oplus \chi$ are $-1$, $-1$, and $1$, and hence the eigenvalues of $W$ are $1$ and $-1$. Hence you get deformations if $\ell \equiv \pm 1 \mod p$.
In either of these cases, the existence of deformations gives rise to modular forms, assuming (for example) we are in a context in which $R_{\Sigma} = \mathbf{T}_{\Sigma}$. Those lifts can not all be CM, since otherwise one would not see any cohomology coming from $W$.
If you want to insist, for example, that the newforms have level structure $\Gamma(N) \cap \Gamma_0(\ell)$ (rather than $\Gamma_1(\ell)$ or higher powers of the conductor at $\ell$) then you could (for example) insist that $\chi(\Frob_{\ell}) = +1$, that $\ell \not\equiv 1 \mod p$, and the ratio of eigenvalues is $\ell$. Then the only possible local deformations are of Steinberg type, and they exist by 1.
Edit: I just saw that you want to insist that $\ell \equiv 1 \mod p$. Assuming that you also want $\Gamma_0(N \ell)$-level structure, I think one might be in good shape if $\rhobar(\Frob_{\ell})$ is (for example) trivial. Note that primes which split completely have relatively small density, so one might not find them by accident. Just to please Noam, here's an example:
$$E:= [0,0,0,-1,0] \ \text{of conductor $32$ with CM}$$
$$A:= [0,0,0,-332,-2752] \ \text{of conductor $32 \cdot 61$ with no CM}$$
$$D:= [0,0,0,-3256,-67984] \ \text{of conductor $32 \cdot 373$ with no CM},$$
and then $E[3] = A[3] = D[3]$.
Extra: One can also go the high powered route: Khare-Wintenberger lifting theorems allow one to find global lifts (in the potentially diagonalizable situation in which one is in here) as long as one has local lifts. So a lift which is Steinberg at $\ell$ up to twist at level $\Gamma_0(N \ell)$ will exist (assuming $\rhobar$ satisfies the Taylor-Wiles conditions) as long as $\alpha_{\ell}/\beta_{\ell}$ is $\ell$ or $\ell^{-1} \mod p$. Since the lift will be Steinberg at $\ell$, it won't be CM.
