I don't know how to do it in cubic time, but I suppose that, to use Newton's Method, you could do the following:

Find floor(log_{2}*n*), and this is the largest "power" that it can be. Then, define:
$f_k(x) = x^k - n$ where *n* is your number and *k* is the floor value, and iterate Newton's Method until you get a number whose floor is *m* that fits any of the following:

1) *m*^{k} < *n* && (*m*+1)^{k} > *n*

2) *m*^{k} > *n* && (*m*-1)^{k} > *n*

3) *m*^{k} == *n*

If the third is true, congrats, you've found yourself a root! Otherwise, reduce *k* by 1 and try again.

The problem with this is that I don't know how long it'll take for such a value of *m* to be found. Wikipedia says Newton's Method has a quadratic convergence, and you're making a fixed number of operations each iteration of the Method, so I guess its running-time would be pretty fast.