Can one construct a non-measurable set without Axiom of choice?
The answer is, you cannot.
It is consistent with ZF that the real numbers are a countable union of countable sets, this implies that every set of reals is Borel and therefore measurable. Of course, in such model it is nearly impossible to develop the analysis we know.
However it is consistent relative to an inaccessible cardinal that there is a model of ZF+DC where all the sets of real numbers are Lebesgue measurable, and DC allows us to do most of classical analysis too.
Non-measurable sets can be generated by free ultrafilters over $\mathbb N$ too, which as remarked is a strictly weaker assumption that the axiom of choice. If there are $\aleph_1$ many real numbers and DC holds then there is an non-measurable set as well, which implies that ZF+DC($\aleph_1$) also implies the existence of non-measurable sets of real numbers - however this is not enough to imply the existence of free ultrafilters over the natural numbers!
Several other ways to generate non-measurable sets of real numbers:
- The axiom of choice for families of pairs;
- Hahn-Banach theorem;
- The existence of a Hamel basis for $\mathbb R$ over $\mathbb Q$.
There are several other ways as well, but none are quite close to the full power of the axiom of choice.
One important remark is that we can ensure that the axiom of choice holds for the real numbers as usual, but breaks in many many severe ways much much further in the universe (that is counterexamples will be sets generated much later than the real numbers in the von Neumann hierarchy). This means that the axiom of choice is severely negated - but the real numbers still behave as we know them.
The above constructions and to further read about ways to construct non-measurable sets cf. Horst Herrlich, Axiom of Choice, Lecture Notes in Mathematics v. 1876, Springer-Verlag (2006).