Is there a probability measure $\mu$ on $\mathbb{Z}$ such that, for every $0 < \alpha \leq 1$ and every finitely supported (¹) probability measure $\nu$ on $\mathbb{Z}$, it holds that the $\alpha \mu + (1-\alpha)\nu$-random walk on $\mathbb{Z}$ is recurrent? It seems like $\mu(n) = C/(1+n^2)$ is a good candidate.
(¹) Added in edit
It's indeed not so clear (to me) if one can have a recurrent random walk with a measure that doesn't have an expectation, but the answer to your actual question is no (and it's quite a bit more subtle than I thought originally, in my naïve comment). We obtain precise criteria from versions of the law of large numbers for random variables with $E|X_j|=\infty$, which can be found in this 1973 article by Erickson.
Adapted to your setting, Erickson proves that $\limsup S_n/n=\infty$ if and only if $$ \sum_{n\ge 1} \frac{n}{f(n)}\rho(n)=\infty , \quad f(n):=\int_{-n}^0 \rho((-\infty,x])\, dx \quad\quad\quad\quad (1) $$ (= Theorem 2(a)). Here, $S_n$ denotes the position of the random walk at time $n$, and $\rho$ is the distribution of a single step.
Similarly, the analogous condition $$ \sum_{n\ge 1} \frac{n}{g(n)}\rho(-n)=\infty , \quad g(n):=\int_0^n \rho((x,\infty))\, dx \quad\quad\quad\quad (2) $$ is equivalent to $\liminf S_n/n=-\infty$, and if we have (1), but not (2), then $\lim S_n/n=\infty$ a.s. (this is Theorem 2(c)), which means that the RW is transient.
Now to answer to your question, I claim that given any $\mu$, I will be able to find a $\nu$ such that $\rho=(1/2)(\mu+\nu)$ satisfies (1), but not (2). In fact, (1) is easy because $f(n)=o(n)$, so I just need $\nu(n)$'s not extremely small every once in a while at very large $n$'s.
As for (2), let me assume that $\mu$ is supported by the negative integers (it only gets easier otherwise). Take $N_1$ so large that $\sum_{n\le N_1}\mu(-n)\ge 1/2$. My $\nu$ will be supported by the positive integers, and we now agree that it will give zero weight to $n\le N_1$. Then $g(n)=n/2$ for those $n$. Next, I take $N_2>N_1$ so large that $\sum_{N_1<n\le N_2}\mu(n)\ge 1/4$, and we then agree that $\nu$ gives weight $\le 1/10$ to this interval. This will make sure that $g(n)\ge (9/20)n$, so $n/g(n)$ from the sum from (2) amplifies the $\mu(-n)$'s by at most $20/9$. We can continue in this way. The sum will be finite, and the conditions on $\nu$ that I obtain from this procedure only require me to move much of the weight very far out, which is not interfering with (1) (in fact, it's helping me).
Contrary to the common opinion, it is not true that any random walk with infinite first moment on $\mathbb Z$ is transient. Example E2 on p.87 of the second edition of Spitzer's book Principles of Random Walks shows that for the probability measures $\mu$ on $\mathbb Z$ such that $$ |n|^\alpha\mu(n) = c + o(1) \qquad \text{with} \;c>0 $$ the random walk $(\mathbb Z,\mu)$ is recurrent if and only if $\alpha\ge 2$. However, for $\alpha=2$ the first moment of the measure $\mu$ is infinite (this is precisely the situation the OP is referring to). In fact, Spitzer further (in example E3) gives a very explicit example of a recurrent measure with an infinite first moment (which also satisfies the above formula with $\alpha=2$). This is the step distribution of the random walk on the diagonal $\{(n,m)\in\mathbb Z^2: n=m\}$ induced by the simple random walk on $\mathbb Z^2$.
Now, returning to your question about "robustness". The answer is no. Moreover, it is the transience that is "robust" in your sense. The reason is a comparison criterion for recurrence/transience of general Markov chains (Theorem 2.25 in Woess' book Random Walks on Infinite Graphs and Groups). In the group setup it implies that if the random walk on a group $G$ determined by the measure $\alpha\mu +(1-\alpha)\nu$ is recurrent and the measure $\nu$ is symmetric, then the random walk $(G,\nu)$ is also recurrent. Or, in other words, if $(G,\nu)$ is transient for a symmetric $\nu$, then $(G,\alpha\mu +(1-\alpha)\nu)$ is also transient for any $\mu$ and any $\alpha<1$.
