If you mean that $H$ is a subgroup of $\mathbb{Z}\oplus\mathbb{Z}$ where each $h=\left[\matrix{a\\b}\right]\in H$ satisfies the condition $b=0\implies a=0$, then you have a tractable problem.
In this case, a hint is to consider the smallest positive value that $a$ can have over all such $h$ above.
You could define $\alpha=\inf_{h\in H}|\pi_1(h)|$ where $\pi_1:H\to\mathbb{Z}$ is the "projection" homomorphism $h\mapsto a$ taking each $h$ to its first ordinate. Or, if this seems to abstract, start by observing that the set $A=\{a~|~h\in H\}$ is itself a subgroup of $\mathbb{Z}$, then let $A^+=\{a\in A~|~a > 0\}$ and $\alpha=\inf A^+$.
Then, let $g=\left[\matrix{\alpha\\\beta}\right]$ be a (the) element of $H$ having this minimal positive first ordinate. You will be able to show that $g$ is in fact unique and that it generates $H$, i.e. each $h=ng$ for some $n\in\mathbb{Z}$.
Intuitively, you can visualize this as a (parallelogramic) lattice in $\mathbb{Z}^2$, or as an additive subgroup (in fact, an ideal) $I=\left<\alpha+i\beta\right>$ in the ring of Gaussian integers.
To make the formal proof, you could use Bézout's identity as Simon Markett does. Or, you can notice that the minimality condition defining $\alpha$ is in fact an equivalent way of defining the greatest common divisor. Then, notice that $\pm\alpha$ are the unique generators of $H_1=\pi_1(\mathbb{Z})$ which is a cyclic subgroup of the first $\mathbb{Z}$ in $\mathbb{Z}\oplus\mathbb{Z}$, for if some $h$ had $a\not\equiv0\pmod\alpha$, then replacing $a$ with its remainder $r$ would produce an element of $H$ with smaller first ordinate, condtradicting the minimality of $\alpha$.
Lastly, we need to show that $\beta$ as defined above (which may be negative) generates $H_2=\pi_2(H)$, i.e. has minimal absolute value over all second ordinates $b$ of $h\in H$. However we already know that $H_2$ is a cyclic subgroup of $\mathbb{Z}$, and if its generator $\beta'$ were smaller in absolute value than $\beta$, then we would have $\beta'|\beta\implies\beta=n\beta'$ and hence $g=ng'$ for some $g'=\left[\matrix{\alpha'\\\beta'}\right]\in H$ with second ordinate $\beta'$ and some $n\ne0,~\pm1$. But then we would have $\alpha=n\alpha'=|n\alpha'|>|\alpha'|$, contradicting the minimality of $\alpha$.
The key insight in this last step is that the minimality (in absolute value) of $\alpha$ and $\beta$ are linked, or coupled. Thus, we could started by defining $\beta$ as well from a minimality condition, analogously to $\alpha$, and then proving that one of $\left[\matrix{\alpha\\\pm\beta}\right]$ generates $H$.