Every known construction of the Vitali set relies on the Axiom of Choice. It happens to not be Lebesgue-measurable.
Must every set whose construction relies on the Axiom of Choice not be Lebesgue-measurable?
I'm not sure if "relies on the Axiom of Choice" is mathematically meaningful, in which case I'll rephrase the question as asking whether there are any sets for which there is an existence proof with AC but no known existence proof without AC, which are known to be Lebesgue-measurable.
This related question asks whether there exists a Lebesgue non-measurable set that can be constructed without AC. The answer to that question is no.
The answer is negative.
An easy example is subsets of the Cantor set which have null measure, but can be "very non measurable". But this is sort of cheating since the Cantor set can be endowed with its own measure which is isomorphic to the actual Lebesgue measure on the unit interval, and there these subsets of the Cantor set need not be measurable themselves.
But there is an alternative. It is a nice theorem that the continuous image of a closed set Lebesgue measurable. Such set need not be a Borel set, and it is called an analytic set. But it is also consistent without the axiom of choice that every set is a Borel set, in which case there are no analytic sets which are not Borel.
So an analytic set would be Lebesgue measurable, but you need the axiom of choice to prove there is one which is not Borel.