View $\overline{\rho}$ as a representation

$$\overline{\rho}: G_{\mathbb{Q}} \rightarrow
\mathrm{PGL}_2(\overline{\mathbb{F}}_p).$$

The obstruction to lifting this to a Galois representation with values in $\mathrm{GL}_2(\overline{\mathbb{F}}_p)$ lies in $H^2(\mathbb{Q},\overline{\mathbb{F}}^{\times}_p)$, but this vanishes by a theorem of Tate (here we use the fact that we have extended scalars so that the coefficients are divisible).

Now consider the lifted representation

$$\rho: G_{\mathbb{Q}} \rightarrow \mathrm{GL}_2(\overline{\mathbb{F}}_p).$$

If the image of complex conjugation in $\overline{\rho}$ is non-trivial, then the image in the lift will be non-scalar, and vice versa. Hence Serre's conjecture implies that all such "odd" (complex conjugation is non-trivial) representations come from modular ones.

Some extras: using the fact that the class number of $\mathbb{Q}$ is one, one can twist this representation so that it is unramified at all primes where $\overline{\rho}$ itself is unramified. In fact, examining Tate's theorem more closely, one can even find a lift such that, given any *local* lift $\varrho$ (a representation of the decomposition group $D_q$ of $\mathbb{Q}$) of $\overline{\rho}|_{D_q}$, one may insist that

$$\rho |_{I_q} = \varrho |_{I_q}.$$

By this result, working out the invariants $N(\rho)$ and $k(\rho)$ associated to $\overline{\rho}$ is a purely local problem. In particular, there is indeed a corresponding projective version of Serre's conjecture (now a theorem, of course!)

Note that, in general, finding a lift will require increasing the coefficient field from $\mathbb{F}_p$ to some finite extension. (If the corresponding class in $H^2(\mathbb{Q},\mathbb{F}^{\times}_p)$ is non-zero, there will never be a lift valued in $\mathrm{GL}_2(\mathbb{F}_p)$. Of course all lifts are twists of each other.)

One warning: for local reasons, it might be the case that any such lift $\varrho$ is *more* ramified at $q$ than $\overline{\rho}|_{D_q}$ is (this only happens if the latter is ramifed, of course, since unramified representations always have unramified lifts). This happens, for example, if the projective image of $D_q$ has image the Klein $4$-group $K$. (The projective image associated to an abelian representation will be projectively equivalent to $1 \oplus \chi$ and so have cyclic projective image. Hence the lift of any projective faithful representation of $K$ will be non-abelian. However, if the lift came from an extension with no more ramification, it would have to be abelian.)

One reference for some of these remarks is Serre's paper on weight one modular forms which I think is from some point in the '70s. (Serre is working with complex projective representations, but the arguments are pretty much the same.)

(Ah, I now realize this question is from 2014, sorry.)