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.)