Hatcher's book also proceeds by first showing that there is the power operation $P(x)$ as you say, and he proves all the properties.

[Hatcher makes a bit of use of the fact that cohomology is represented by Eilenberg MacLane spaces, but one can avoid this. I have unpublished Latexed notes of my own that I have given out to Virginia's algebraic topology students for many years that take this approach. I don't have access to Haynes' book, so I don't know how much homotopy theory he uses.]

A couple of things to note:

(a) $P$ is not linear: $P(x+y) - P(x)-P(y) = tr(x \otimes y)$, where $tr: H^*(X^2) \rightarrow H_{C_2}^*(X^2)$ is the transfer associated to the double covering $EC_2 \times X^2 \rightarrow EC_2 \times_{C_2}X^2$. But this `error term' can be seen to map to zero under the pullback to $BC_2 \times X \rightarrow EC_2 \times_{C_2}X^2$, using standard properties of the transfer.

(b) The property that is arguably the most subtle to prove is that $Sq^0$ acts as the identity on a one dimensional class. (From this, then one deduces that $Sq^0$ is the identity in general.)

Hatcher's book also proceeds by first showing that there is the power operation $P(x)$ as you say, and he proves all the properties.

Hatcher makes quite a bit of use of the fact that cohomology is represented by Eilenberg MacLane spaces, but, with care, one can avoid this, though one needs a bit of homotopy theory to show that to define $P(x)$ for all $x \in H^n(X)$ and all spaces $X$, it suffices to define it assuming that $X$ satisfies $H^m(X) = 0$ for $m<n$. I have unpublished Latexed notes of my own that I have given out to Virginia's algebraic topology students for many years that take this approach, and avoids Haynes' use of the Serre Spectral Sequence.

A couple of things to note:

(a) $P$ is not linear: $P(x+y) - P(x)-P(y) = tr(x \otimes y)$, where $tr: H^*(X^2) \rightarrow H_{C_2}^*(X^2)$ is the transfer associated to the double covering $EC_2 \times X^2 \rightarrow EC_2 \times_{C_2}X^2$. But this `error term' can be seen to map to zero under the pullback to $BC_2 \times X \rightarrow EC_2 \times_{C_2}X^2$, using standard properties of the transfer.

(b) The property that is arguably the most subtle to prove is that $Sq^0$ acts as the identity on a one dimensional class. (Looking at Haynes' notes, I see that this is a property he proves carefully.)