Finding the cube root of a number using integer arithmetic only?

Yes, there is an obvious procedure that will find the floor of the cube root of a positive integer $n$ rapidly and certainly. One maintains an approximation $a_i$ that is certain to be greater than the true cube root $\sqrt[3]n$. One could initially take $a_0=n$, but somewhat more sophisticated approximations will do a lot better; for instance the first power of $2$ to exceed $\sqrt[3]n$ is easy to give immediately if one has access to the number of binary digits of $n$, and fairly quickly found even if one doesn't. Now compute $$ a_{i+1}=\left\lfloor\frac{2a_i+\lfloor n/a_i^2\rfloor}3\right\rfloor =\left\lfloor\frac{2a_i+ n/a_i^2}3\right\rfloor $$ (the first expression shows it only involves integer division, but the one on the right is easier for reasoning, and both are easily seen to be equal). Now $a_{i+1}^3\leq n$ then $a_{i+1}$ is the required answer (because the arithmetic mean of $(a_i,a_i,n/a_i^2)$ is greater than their geometric mean $\sqrt[3]n$, so the inequality can only hold due to application of the floor function), and otherwise $\sqrt[3]n<a_{i+1}<a_i$ ensures that we have improved our estimate, so we can iterate. The actual iteration is a one-liner

while a^3>n do a:=(2*a+n/a^2)/3 od

in any programming language that has arbitrary-length integers.

In fact the convergence becomes considerably better than binary search as $a_i$ approaches $\sqrt[3]n$. Experimentation with numbers of more than $100$ digits shows that once one has got an approximation that is no more than twice as large as $\sqrt[3]n$ (as the power-of-two initialisation would provide), then every next approximation has about twice as many digits correct as the previous one. It would be an instructive exercise (in other words I'm too lazy) to show this rigorously.

There is a "long division" type algorithm for cube root similar to that for square root. See http://en.wikipedia.org/wiki/Shifting_nth-root_algorithm But binary search is easier to implement and just as fast.