A relative compactness criterion in $\ell^p$ There is a relative compactness criterion for subset of $\ell^p$ that seems to me to be almost unheard-of (I say that because a google search provided no proofs nor references) but that is very useful:

Theorem. For any $p$, $1\leq p < \infty$, a bounded subset $K$ of $\ell^p$ is relatively compact if and only if $\displaystyle\lim_{n_\epsilon} \sum_{i=n_\epsilon}^\infty \vert k_i \rvert^p = 0$, uniformly for $k \in K$. 

This theorem is assigned as exercise in Diestel (see below) and is widely applied in Costara-Popa in order to prove relative compactness in $\ell^p$ (a classical example is to show that the operator $T : \ell^p \to \ell^p$ defined by $( T a )_n = \lambda_n a_n$ for all $a \in \ell^p$ is compact iff $(l_n) \in c_0$). However, I founded its proof rather tricky.
My idea is essentially showing that a subset such as in theorem is totally bounded. (since in this way the result follows by well-established equivalence between totally boundeness and relative compactness in metric spaces.) Thus, chosen $\epsilon >0$, I was looking for a finite collection $S$ of vectors in $\ell^p$ such that every vector in $K$ is far from at last one vector in $S$ less than $\epsilon$. 
The condition in theorem means that, fixed $\eta > 0$, there exists $n_\eta \in \mathbb N$ s.t. $\sum_{i=n}^\infty \lvert k_i \rvert^p < \eta^p$ and $n_\eta$ is the same for all $k \in K$ (depending only on $\eta$). Furthermore, since $K$ is bounded, there exists $M>0$ s.t. $\lVert k \rVert_p \leq M$ for all $k\in K$. So I'd consider a collection of vectors $u^{(j)}$ that have only $n_\eta$ non-zero components and set their values in such a way that
\begin{equation}
\lVert k- u^{(j)} \rVert_ p^p = \sum_{i=1}^\infty \lvert k_i - u_i^{(j)} \rvert^p =\sum_{i=1}^{n_\eta} \lvert k_i - u_i^{(j)} \rvert^p + \sum_{i=n_\eta}^\infty \lvert k_i \rvert^p < \epsilon^p
\end{equation}
Since the second summation in the third term is less than $\eta^p$ (and $\eta$ could be arbitrary small, in particular smaller than $\epsilon$), it remains only to show that it is possible to have $\sum_{i=1}^{n_\epsilon} \lvert k_i - u_i^{(j)} \rvert^p \leq \epsilon^p - \eta^p$. Set $r^p = \frac{\epsilon^p - \eta^p}{n_\eta ( M+1 ) }$ and choose $N \in \mathbb N$ s.t. $Nr^p \geq M$. Suppose that each component of $u^{(j)}$ takes one of the $2N + 1$ values $0, \pm r^p, \pm 2r^p, \dots, \pm N r^p$. Since $-M \leq k_i \leq M$ for every $i \leq n_\eta$, there exists an integer $C$ with $-N + 1 \leq C \leq N$ s.t. $(C - 1 )r^p \leq k_i \leq C r^p$. Then set $u_i^{(j)} = C r^p$. Thus
\begin{equation}
\sum_{i=1}^{n_\epsilon} \lvert k_i - u_i^{(j)} \rvert^p < \epsilon^p - \eta^p
\end{equation}
by construction. Now, the number of different vectors $u^{(j)}$ we can construct in this way is finite when $\eta$ and $\epsilon$ are fixed, hence $K$ is totally bounded.
I think this attempt works (I have adapted the proof of compactness of Lipschitz functions space in bounded functions space found in an italian book of mathematical analysis), but at the same time it seems to be rather messy. I valued other possibilities (such as apply the Ascoli-Arzelà theorem), but this one appeared to be the most promising. So I wonder if there are other clearer proofs or references in which this theorem is proved.
References. 
J. Diestel, Sequences and series in Banach spaces, chp 1, ex 6,
C. Costara, D. Popa, Exercises in Functional Analysis.
 A: A general strategy to prove compactness is the following: Look for a coarser (Hausdorff) topology in which the set is compact and prove that both topologies
coincide on the given set. (Since on a compact set there is no strictly coarser
Hausdorff topology, at least in principle, this strategy always works).
The compactness in the coarser topology will almost always follow from Tychonov's theorem (and the compactness of intervals in $\mathbb R$).
In your case, you can take either the weak* topology ($\ell^p=(\ell^q)^*$ for $p>1$ and $\ell^1=c_0^*$) or the product topology on $\mathbb R^\mathbb N$.
The weak* compactness comes from Alaoglu's theorem which is a direct consequence of Tychonov's and the coincidence of both topologies uses the assumption (for each $\varepsilon>0$ you only have to deal with finitely many coordinates).
As you hoped to apply Arzela-Ascoli: Note that this again can be proved by the strategy: Pointwise boundedness gives you compactness in a big product via Tychonov and equicontinuity yields the coincidence of topologies. 
A: We get a shorter proof if we use the characterization of totally bounded sets given here, a set $K$ is totally bounded if and only if for every $\varepsilon > 0$ there is a compact set $C$ such that $d(x,C) < \varepsilon$ for all $x \in K$.
Then, for $n \in \mathbb{N}$ consider the projection
$$P_n \colon \ell^p \to \ell^p;\quad P_n(x)_m = \begin{cases}x_m &; m \leqslant n\\ 0 &, m > n. \end{cases}$$
For the given $K$, and $\varepsilon > 0$ choose $n_\varepsilon$ such that
$$\sum_{n = n_\varepsilon}^\infty \lvert k_n\rvert^p < \varepsilon^p/2$$
for all $k \in K$. Then let $C = \overline{P_{n_\varepsilon}(K)}$. $C$ is a closed and bounded set in a finite-dimensional space, hence compact. By choice of $n_\varepsilon$, we have $\lVert k -P_{n_\varepsilon}(k)\rVert_p < \varepsilon$ for all $k \in K$, and $P_{n_\varepsilon}(k) \in C$.
So the criterion is satisfied, hence $K$ is totally bounded.
This criterion for relative compactness in $\ell^p$ is the easier cousin of the theorem of Fréchet and Kolmogorv characterising the relatively compact sets in the $L^p$ spaces.
