I have a matrix $A \in \mathbb{R}^{n \times m}$ implicitly defined (i.e. for which I can calculate the matrix-vector products $Ax$ and $A^T x$, but storing the entire matrix is prohibitive in terms of memory).
What is a fast numerical algorithm to only compute the smallest non-zero singular value for $A$? Note that memory requirements for the algorithm should be $O(m+n)$, since storing the entire matrix is not feasible.
This is too long for a comment, so I'll post it as an answer. What you're hoping to do is very challenging. Part of the reason power iteration and its cousins work so well is that iterative multiplications by a symmetric matrix converge very quickly to the dominant eigenvectors, making the small eigenvectors very challenging to find just by multiplications.
The best algorithm I can think of is to, as Ben Grossmann suggested, do inverse iteration to compute the eigenvalues of $A^\top A$ and then take square roots. Linear systems of the form $(A^\top A)x = b$ can then be solved by the conjugate gradient method. Each inverse iteration loop requires $\mathcal{O}(M\kappa(A) \log(1/\epsilon))$ operations where $M$ is the time to multiply by $A$ and $A^\top$, $\kappa(A)$ is the condition number of $A$, and $\epsilon$ is the accuracy desired for the CG solves. Then you'll need something like $\mathcal{O}(\log (1/\epsilon)/\log(\sigma_1(A)/\sigma_2(A)))$ iterations to achieve accuracy $\epsilon$. My sense is that it's hard to do better than this, but I hope to be proven wrong.