Hensel lemma - generalization?

Yes, and this is not a generalization of Hensel's lemma.

We will repeatedly pass to subsequences as follows. First, the set $R_1 = \{ a_n \bmod p \}$ has finitely many elements, so there must be some residue $r_1 \in R_1$ such that there are infinitely many $n$ with $a_n \equiv r_1 \bmod p$. Pass to this subsequence; that is, assume WLOG that every $a_n$ has this property (mostly in order to avoid having to come up with some annoying piece of notation for the new subsequence).

Next construct $R_2 = \{ a_n \bmod p^2 : n \ge 2 \}$, which again is finite, so again there is some residue $r_2 \in R_2$ such that there are infinitely many $n$ with $a_n \equiv r_2 \bmod p^2$. Again pass to this subsequence. Etc.

In this way we construct a sequence of residues $r_k \in \mathbb{Z}/p^k\mathbb{Z}$ such that $r_k \equiv r_{k-1} \bmod p^{k-1}$ and such that there exist infinitely many $a_n$ such that $a_n \equiv r_k \bmod p^k$. The $r_k$ define an element $r \in \mathbb{Z}_p$ which is a root of $f$. Note that we don't need to assume that $f$ is monic.

Consider $f$ as a map $\mathbb{Z}_p\to\mathbb{Z}_p$. Since $f$ has a root mod $p^n$ for all $n$, the image of $f$ contains points arbitrarily close to $0$ in the $p$-adic metric. But $f$ is continuous and $\mathbb{Z}_p$ is a compact Hausdorff space, so the image of $f$ must be closed. Thus $0$ is in the image of $f$, i.e. $f$ has a root in $\mathbb{Z}_p$.

(If you unwind this proof it's essentially the same as Qiaochu's, but the topological language really makes it very simple!)