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(log2n), 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) mk < n && (m+1)k > n
2) mk > n && (m-1)k > n
3) mk == 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.