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).