A group $G$ with the property is called sequencable. For a survey, see this paper by M. A. Ollis, which also tells that sequencable groups are related to constructing row-complete latin squares. It is conjectured by Keedwell that $D_6,D_8$ and $Q_8$ are the only non-abelian non-sequencable groups (see page 17); in particular, there should be none with odd order. It is known that an abelian group is sequencable if and only if it has a unique element of order 2 (see page 5 for a proof). The article gives a list of groups that are known to be sequencable. Apparently the question is not completely solved even in the case where $|G|$ has two prime factors.
However, some groups of odd order are known to be sequencable, so an example to your question would be for instance the non-abelian group of order 21 (page 5; there are other examples as well).