I have a holomorphic function $f(z)$ which is "near" $\cos z$ in the sense that as $z\to\pm i\infty$, $f(z)$ is dominated by the exponential behavior of $\cos z$. For example $f(z)=\cos z+a$ or $f(z)=\cos z+1/z$. I would like to prove that $f(z)$ has an infinite number of zeros.
Intuitively, I would like to argue as follows: Let $\gamma$ be a straight line path from $z$ to $z+2\pi$, where $\Im(z)$ is large positive. Then $f(\gamma)$ traces out a large circle clockwise around the origin with winding number approximately $-1$. If we decrease $\Im(z)$ this path does something complicated, but as $\Im(z)$ becomes large negative it settles back to an approximate circle around the origin, this time traced counterclockwise, so the winding number is now approximately $1$, and at some point the path had to cross the origin in order to change the winding number.
I realize this proof sketch is problematic, because the path isn't closed, so the origin can "escape" the sweep that way. I think there is a standard technique in complex analysis for this but I'm not sure how to apply it. I am being slightly vague about the function $f$ because I'm not sure what properties I need it to satisfy for this theorem to hold, if the ones I have given are insufficient.
For a proof in general you need to state the hypothesis more clearly. Guessing what you mean, it seems to me that $f(z)=e^{iz}$ is "dominated by the exponential behavior of $\cos(z)$ as $z\to\pm i\infty$", but it has no zero.
The two explicit examples you give are easy:
There exists $w$ such that $(w+1/w)/2=-a$. We certainly have $w\ne0$, hence there exist infinitely many $z$ with $e^{iz}=w$, hence $\cos(z)=-a$.
Note that if $|a|\ge1$ then this one cannot be done by Rouche. Because if $\cos(p)=0$ there is no bounded open set $U$ with $p\in U$ such that $|a|<|\cos(z)|$ on the boundary. I mention this because it may be relevant to the general case, if you ever determine exactly what the general case is.
Say $p_1,p_2,\dots$ are the zeroes of $\cos(z)$. Say $\gamma_n$ is a circle with center $p_n$ and radius $1$. There exists $\delta>0$ such that $|\cos(z)|\ge\delta$ on $C_n$. If $n$ is large enough then $|1/z|<\delta$ on $C_n$. Rouche.