The problem isn't really about the existence of algorithms: The required coprime integers $a$ and $b$ can be found by a systematic search if they exist at all, assuming any reasonable interpretation of the word Given in the first sentence of the question.
It will simplify matters to divide the inequality in the first sentence by $x$.
With this in mind, I'll give a proof of the following assertion:
Let $\epsilon>0$.` Suppose $a$ is irrational and $b$ is any real number. Then there are coprime integers $x$ and $y$ such that $|ax-y-b|<\epsilon$.
Proof: The proof has undergone a major rewrite, thanks to Gerry Myerson's helpful comments.
The argument extends a similar result (not mentioning coprimality) proved in Khinchin's book on continued fractions, which is a good reference for the basic facts I'll use here.
Let $p/q$ be a convergent (to be specified later) of the continued fraction expansion of $a$. Then it is well known (see Khinchin) that $p$ and $q$ are coprime, and moreover that $|a-p/q|<1/q^2$.
The latter inequality implies that for some real number $\delta$ with $|\delta|<1$,
$$a=\frac{p}{q}+\frac{\delta}{q^2}.$$
We will now produce a peculiar-looking estimate for $b$, the reason for which will become apparent shortly. Note that without loss of generality we can and will take $b$ to be positive.
Let $t$ be the largest prime not larger than $bq$. Then by Bertrand's Postulate $t\le bq<2t$. From this we deduce the following chain of inequalities:
$$t/q\le b<2t/q\le t/q+b.$$
It follows that for some $\gamma$ with $0\le \gamma <b$,
$$b=\frac{t}{q}+\frac{\gamma}{q}.$$
Thus, for any integers $x$ and $y$, we have the equality
$$|ax-y-b|=\left|\left(\frac{p}{q}+\frac{\delta}{q^2}\right)x-y-\left(\frac{t}{q}+\frac{\gamma}{q}\right)\right|.$$
The right hand side can be rewritten as
$$\left|\frac{px-t}{q}-y +\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|,$$
and the latter is at most
$$\left|\frac{px-t}{q}-y\right| +\left|\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|.$$
Therefore to complete the proof it is enough to choose $q, x, y$ such that
(1) $x$ and $y$ are coprime.
(2) $\displaystyle\frac{px-t}{q}-y=0$, or equivalently $px-qy=t$.
(3) $\displaystyle\left|\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|<\epsilon$.
Now since $p$ and $q$ are coprime, the equation $px-qy=t$ has integer solutions, say $x=x_0$ and $y=y_0$. For every integer $z$ there are additional solutions $x=x_0+qz$ and $y=y_0+pz$. Therefore we can choose solutions $x_0,\,y_0$ with $x_0$ in the interval $[0,q)$.
If $x_0$ and $y_0$ are not relatively prime, then since $px_0+qy_0=t$, and since $t$ is prime, it follows that $t$ is the only possible common factor. But if $t$ is in fact a common factor, then $x_0+q$ and $y_0+p$ must be relatively prime, because $t$ is likewise the only possible common factor of $x_0+q$ and $y_0+p$: But $t$ cannot divide these two integers lest $t$ divide both $p$ and $q$.
It follows that for any convergent $p/q$ for the continued fraction expansion of $a$, there are coprime integer solutions $x,\,y$ of the equation $px-qy=t$, with $x$ in the interval $[0,2q)$. For any such $x$, we have
$$\left|\frac{\delta x}{q^2}-\frac{\gamma}{q}\right|<\frac{2}{q}+\frac{b}{q}.$$
Therefore, finally, if we choose $q$ so large that $\frac{2}{q}+\frac{b}{q}<\epsilon$, then Conditions (1) (2) and (3) are satisfied, and the proof is complete.
