To solve this we need to use different machines.
- First of all, we generally have for all spaces: $H^1(X)\neq 0$ implies existence of a homotopically non-trivial $X\to S^1$, because of
$$[X,S^1] =[X, K(\mathbb Z,1)] = H^1(X;\mathbb Z).$$
Now differential topology, more specifically transversality, will give you that the generic preimage of a $k$-submanifold of an $n$-manifold is a $(n-k)$ - codimensional submanifold. In your case that makes a surface.
Putting the first two facts together, we see that as a generic preimage of a point of $f:M\to S^1$ representing $f_*\in Hom(\pi_1M, \mathbb Z)\cong H^1(M)$ gives a two-sided (normal bundle pulls back) properly embedded 1-codimensional submanifold $N\subset M$. $N$ defines a non-trivial 1-codimensional $\mathbb Z/2$-homology class in $M$. Hence there is a connected component $N_0\subset N$ which is homologically non-trivial in $M$. In particular $M-N_0$ is connected.
Next thing you want to do is surgery on $N_0$ --- successively surger out any compression disk you can find. If new trivial/separating components arise: throw them away (here you use the $P^2$-incompressibilty). These surgeries don't change the homology type of $N_0$.
Eventually you obtain your desired surface in $M$.
Note that 1. does not put any assumptions on the space, 2. & 3. work for general smooth manifolds, and only in 4. we actually need $dim(M)=3$.
For further readings on this (at least in the similar case with orientability; you can often either adapt the proofs for the non-orientable case or just ignore everything by substituting $\mathbb Z$ with $\mathbb Z/2$ and adding a primitivity condition) I suggest :