The extension of the 2adic valuation to the reals used in the usual proof uses clearly AC. But is this really necessary ? After all, given a equidissection in $n$ triangles, it is finite, so it should be possible to construct a valuation for only the algebraic numbers, and the coordinates of the summits (with a finite number of "choices"), and then follow the proof to show that $n$ must be even. Or am I badly mistaken ?
No choice is needed. If, in a choiceless universe, there were a counterexample, then that counterexample amounts to finitely many real numbers (the coordinates of the relevant points). It would still be a counterexample in the subuniverse of sets constructible (in Gödel's sense) from those finitely many reals. But that subuniverse satisfies the axiom of choice, so your favorite ZFC proof of the theorem applies there. 


I was recently looking over Monsky's Theorem as supplementary material for my course notes on local fields, and I noticed that his original article (available here) ends by addressing your question:
It is easy to see that extending a rank $1$ valuation from a field $K$ to any monogenic extension $K(t)$ does not use the axiom of choice: if $t$ is algebraic over $K$ the set of extensions is finite, nonempty and explicitly in bijection with $\operatorname{Spec} \hat{K} \otimes_K K(t)$ (and even without AC a finitedimensional $K$algebra must have a maximal ideal!); if $t$ is transcendental over $K$, we may endow $K(t)$ with the Gauss norm, determined on $K[t]$ by $a_n t^n + \ldots + a_0 = \max_i a_i$ and extended to $K(t)$ by multiplicativity. Otherwise put: whereas Andreas Blass's nice answer explains why any proof of this result yields an ACless proof, my answer mentions that Monsky's proof does not really use AC, as pointed out by Monsky. 


This paper (Projective Colorings, by Hales and Straus) seems to imply that the Axiom of Choice is necessary for closely related results. 

