How to find degree of polynomial represented as a circuit?
If the coefficients are small, then for large $x$ the polynomial is roughly equal to $Cx^d$. If you plug in both $x$ and, say, $2x$, then the ratio should be roughly $2^d$. Given bounds on the coefficients and the degree, this method can be made rigorous. 

Another idea uses difference sequences. For a polynomial $P(x) $, the polynomial $P(x+1) - P(x)$ has degree smaller by one,  the polynomial $P(x+2)-2P(x+1)+P(x) $ has degree smaller by two, and so on (in general, the coefficients are binomial coefficients with alternating signs). Using polynomial identity testing you can find the degree by binary search. This seems less efficient than your approach.