Robustly recurrent random walk 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
 A: 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).
A: 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$. 
