Generators of a cyclic group

Yuval's solution, sans Dirichlet: let $n$ be the product of all the primes that divide the order of $G$ but don't divide $x$. Then $\gcd(x+ny,|G|)=1$.

Proof: Let $p$ be a prime dividing the order of $G$. If $p$ divides $x$, then it doesn't divide $y$ (since $\gcd(x,y,|G|)=1$), and it doesn't divide $n$ (by construction), so it doesn't divide $ny$, so it doesn't divide $x+ny$.

If $p$ doesn't divide $x$, then it divides $n$ (by construction), so it divides $ny$, so it doesn't divide $x+ny$. So no prime dividing the order of $G$ divides $x+ny$.

Without loss of generality, $a,b \neq 1$. For $g$ a generator of $G$, we have $a = g^x$ and $b = g^y$, where $(x,y) = 1$. By Dirichlet's theorem, there is $n > |G|$ such that $x + ny$ is prime, so that $(x+ny,|G|) = 1$. Therefore $ab^n = g^{x+ny}$ generates $G$.

Edit: As commented below, we actually only know that $d=(x,y)$ is relatively prime to $|G|$. By Dirichlet's theorem, there is $n > |G|$ such that $(x+ny)/d$ is prime, and so $(x+ny,|G|)=1$.