No, it is not possible. It is consistent with ZF without choice that
the reals are the countable union of countable sets. (*)
From this it follows that all sets of reals are Borel. Of course, the "axiom" (*) makes it impossible to do any analysis. As soon as one allows the bit of choice that it is typically used to set up classical analysis as one is used to (mostly countable choice, but DC seems needed for Radon-Nikodym), one can implement the arguments needed to show
(**) The usual hierarchy of Borel sets (obtained by first taking open sets, then complements, then countable unions of these, then complements, etc) does not terminate before stage $\omega_1$ (this is a kind of diagonal argument).
Logicians call the sets obtained this way $\Delta^1_1$. They are in general a subcollection of the Borel sets. To show that they are all the Borel sets requires a bit of choice (One needs that $\omega_1$ is regular).
There is actually a nice result of Suslin relevant here. He proved that the Borel sets are precisely the $\Delta^1_1$ sets: These are the sets that are simultaneously the continuous image of a Borel set ($\Sigma^1_1$ sets), and the complement of such a set ($\Pi^1_1$ sets).
That there are $\Pi^1_1$ sets that are not $\Delta^1_1$ (and therefore, via a bit of choice, not Borel) is again a result of Suslin. He also showed that any $\Sigma^1_1$ set is either countable, or contains a copy of Cantor's set and therefore has the same size as the reals. His example of a $\Sigma^1_1$ not $\Delta^1_1$ set uses logic (a bit of effective descriptive set theory), and nowadays is more common to use the example of the $\Pi^1_1$ set WO mentioned by Joel, which is not $\Delta^1_1$ by what logicians call a boundedness argument.
A nice reference for some of these issues is the book Mansfield-Weitkamp, Recursive Aspects of Descriptive Set Theory, Oxford University Press, Oxford (1985).
In the 1960's, Bob Solovay constructed a model of ZF + the axiom of dependent choice (DC) + "all sets of reals are Lebesgue measurable." DC is a weak form of choice, sufficient for developing the "non-pathological" parts of real analysis, for example the countable additivity of Lebesgue measure (which is not provable in ZF alone). Solovay's construction begins by assuming that there is a model of ZFC in which there is an inaccessible cardinal. Later, Saharon Shelah showed that the inaccessible cardinal is really needed for this result.
Best Answer
No, the existence of a non-Lebesgue measurable set does not imply the axiom of choice. If ZF is consistent, then set-theorists can construct models of ZF having a non-Lebesgue measurable set, but still not satisfying AC.
This is quite reasonable, because the existence of a non-Lebesgue measurable set is a very local assertion, having to do only with sets of reals, and thus can be satisfied with a small example, by set-theoretic standards. The axiom of choice, in contrast, is a global assertion insisting that every set, even a very large set, has a well-order. So we don't expect to turn a mere non-measurable set into well-orderings of enormous sets, such as the power set $P(\mathbb{R})$.
And indeed, one can use forcing to produce a model $L(P(\mathbb{R})^{V[G]})$ which satisfies $ZF+\neg AC$, for similar reasons as in the usual $\neg AC$ models, but since it has the true $P(\mathbb{R})$, it will have all the same non-Lebesgue measurable sets as in the ambient ZFC universe $V[G]$.
(Finally, let me make a minor objection to the question: consistency is a symmetric relation, and so if $A$ is consistent with $B$, then $B$ would be consistent with $A$, and so one wouldn't ordinarily speak of a "converse". You seem instead to be refering to the implication that AC implies there is a non-measurable set, and this is how I took your question.)