Is there any example of a non-measurable set whose proof of existence doesn't appeal to the Axiom of choice? Is there any example of a non-measurable set whose proof of existence doesn't appeal to the Axiom of choice?
What would it imply if there was such an example?
EDIT: For instance, maybe this will help understand the kind of example I had in mind, it is known that an important feature to determine that the AC is needed in the Banach-Tarski case is the non-transitivity of rotations on Euclidean space, one might find an example of a transitive group for some given space keeping the rest equal and make the AC unnecessary?
I guess then it might be said that this transitivity will be in this particular case equivalent to the AC or some amount of it, but I guess that it would be important to show this if it hadn't been realized before.
 A: Yes.
Or more precisely, 

Theorem: We can explicitly construct in ZF a set $S$ that ZF cannot prove to be measurable.

The set $S$ could then be proven non-measurable by assuming a suitable choice principle. So the role of choice is not in the existence of the set $S$, but in the proof it is nonmeasurable.

The proof of this theorem involves the constructible universe. In particular, one can explicitly define in ZF a well-ordering on the class of constructible sets.
One can construct $S$ by carrying out one's favorite construction of a non-measurable set inside the constructible universe, using the aforementioned 
explicitly constructible well-ordering instead of invoking the well-ordering theorem.
One cannot prove in ZF that $S$ is actually a non-measurable set. However, you can do so if you further assume the axiom of constructibility.
A: No, there is not - it is consistent with ZF that every set of reals is Lebesgue measurable, so some amount of the axiom of choice is needed.
This is even true if we assume dependent choice, a certain reasonably strong choice property (enough to do most useful theorems from analysis): this was proved by Solovay. He needed an additional assumption, though: that the theory ZFC+"There is an inaccessible cardinal" is consistent. It was later shown by Shelah to be necessary: we can prove that ZF+"There is an inaccessible cardinal" is consistent if and only if ZF+DC+"All sets of reals are measurable" is consistent.
In lieu of choice, I believe the consistency of ZF+"All sets of reals are measurable" from merely the consistency of ZF (the weakest possible assumption here) was proved by Truss. However, it's worth pointing out that in ZF alone, "measurable" doesn't necessarily mean what you think. For example, it's consistent with ZF that $\mathbb{R}$ is a countable union of countable sets, and in that context basic analytic properties like measurability go absolutely bonkers. So really the right base theory to look at, in my opinion, is ZF+DC; and then it's a very interesting fact that an inaccessible is needed.
A: I think bof's interpretation of my original question is reasonable. I'm compelled to the following argument as an anwer to it in those terms but I'm certainly no set theorist so any correction is welcome: It seems to me that an affirmative answer would imply that ZF is not powerful enough to produce proofs about set measurability without the aid of the AC, probably because the AC (or the relavant part of it that bears on measurability) may be a direct consequence of the primitive notion of set that is needed to construct the ZF axioms and therefore ZF without an explicit extra axiom like AC cannot prove the existence of such an unmeasurable set. Unfortunately this would mean this affirmative answer could not be proved within ZF so it ultimately has to appeal to the AC wich would actually answer the original answer in the negative,  leading to a situation of undecidability of the question within ZF to avoid contradiction.
