This is not an answer to your question. Rather, it is a "less mysterious" version of the Milnor-Stasheff construction of the Stiefel-Whitney classes, which doesn't refer explicitly to Steenrod operations. (I think I learned about this from my thesis advisor when I was a lad ... it was so long ago ...)
Let $V\to X$ be a real vector bundle. Let $S^\infty=\bigcup S^n$, the infinite dimension sphere. Taking product with $S^\infty$ gives a vector bundle $V\times S^\infty\to X\times S^\infty$. I produce a vector bundle $V'\to X\times RP^\infty$ by dividing out by an action of the cyclic group of order $2$ on both base and total space:
- on the base $X\times S^\infty$, the involution is $(x,y)\mapsto (x,-y)$;
- on the total space $V\times S^\infty$, the involution is $(v,y)\mapsto (-v,-y)$.
The Euler class $e(V')$ of $V'$ is an element of degree $n$ in $H^*(X\times RP^\infty; Z/2) = H^*(X;Z/2)[t]$. The following formula holds:
$$ e(V') = t^n + w_1(V)t^{n-1}+\cdots + w_n(V).$$
So if you have an Euler class, then you can use this as the definition of the Stiefel-Whitney classes. The mod-2 Euler class is fairly easy to define from Milnor-Stasheff's point of view: $e(V')$ is the pullback along the $0$ section of the orientation class in the cohomology of the Thom space of $V'$.
It's easy to check the axioms for this guy. It's certainly natural, since $V\mapsto V'$ and $e$ are functorial. Whitney sum follows from $(V\oplus W)'\approx V'\oplus W'$ and the Whitney sum formula for the Euler class. If $R\to *$ is the trivial bundle, then $R'\to RP^\infty$ is the canonical line, so $e(R')=t$ and so $w_0(R)=1$ and $w_1(R)=0$. You can use this to show that $w_0(V)\in H^0X$ is equal to $1$ for any bundle over $X$, by pulling back $V$ over any point of $X$ (where it becomes trivial). If $L\to RP^\infty$ is the canonical line, then $L'\to RP^\infty\times RP^\infty$ is $L_1\otimes L_2$, the tensor product of the canonical line bundles over each factor. So $e(L')=s+t= 1\cdot t^1 + s\cdot t^0$, giving $w_0(L)=1$ and $w_1(L)=s$ (where $s\in H^1RP^\infty$ is the generator).
Added later. I wrote the above while I was a bit feverish :). It didn't occur to me when describing it that it's a pretty standard way to construct characteristic classes; the variant which gives chern classes is probably more familiar.
I also said that it's a "version" of the Steenrod operation construction of SW classes, so let me try to explain that. I'll sketch a "direct" proof that the Steenrod operation definition of SW classes is equivalent to the one I gave above (i.e., without refering the axioms that M-S give for SW classes).
Steenrod operations come from an "extended square" construction on cohomology classes (see my answer in Why does one think to Steenrod squares and powers?). If $X$ is a space, let $DX=(X\times X \times S^\infty)/(Z/2)$, where I divide by the involution $(x_1,x_2,y)\to (x_2,x_1,-y)$. The "extended square" is a function
$$P: H^n(X) \to H^{2n}(DX).$$
Cohomology is with mod-2 coefficients. If you restict along the "diagonal" embedding $d: X\times RP^\infty \to DX$, you get Steenrod squares:
$$d^*(P(a)) = t^{n}Sq^0(a) + t^{n-1}Sq^1(a) + \cdots + Sq^n(a).$$
There's a relative version of this: if $V\to X$ is a vector bundle, so is $DV\to DX$; write $T(V)$ for the Thom space of $V$, and write $f: T(V) \to T(DV)$ for the map induced by diagonal inclusion. If $u\in H^nT(V)$ is the orientation class, then
$$f^*(P(u))= t^{n}Sq^0(u)+t^{n-1}Sq^1(u)+\cdots +Sq^n(u).$$
According to Milnor-Stasheff, $Sq^i(u)=u\,w_i(V)$.
The neat fact is that $P(u)\in H^{2n}T(DV)$ has to be the orientation class $u'$ of $DV\to DX$! So as long as I can describe the orientation class, I don't need to know about Steenrod opeartions! Thus, $f^*(u')\in H^*TV[t]$ is the polynomial whose coefficients are the SW classes. To get the formula I gave originally, observe that $f^*(u')=u\, e(V')$; this is because the pullback of the bundle $TV\to TX$ along $d: X\to DX$ is the same as the bundle $V+V' \to X$.
Why is $P(u)$ the orientation class of $DV$? The orientation class of a bundle in ordinary cohomology mod-2 is the unique element which restricts to the fundamental class of the sphere when you restrict to each fiber, so you just have to check that $P(u)$ has this property. And this is pretty easy (the operation $P$ is natural, and it's easy to understand how $P$ works when you have a discrete space, or a bundle over a discrete space.)