You're on the right track. You've shown that it can't be cyclic, because cyclic groups are abelian.
The way I see is to proceed to show it by contradiction. Assume G has no element of order 3.
Since G isn't cyclic, G has no element of order 6.
By assumption, G has no element of order 3.
With that information, and |G| = 6, you can determine the orders of G's elements (hint: Lagrange.)
Once you've done that, consider the two elements in G, a and b, that don't commute.
That means that ba is not equal to ab.
The contradiction will appear by looking at g = ab and asking what happens when you square g.
Remember that you'll know something about the order of g at this point - and also the orders of a and b.
So consider what you can say about g squared = abab for those non-commuting a and b.
With a little bit of manipulation when considering g squared, the contradiction will appear.
(The contraction will arise by showing that a and b do commute.)
Thus the assumption was false, and so G has an element of order 3.