Just determine the coefficient at the highest power first by plugging in huge numbers and doing binary search (comparing to what you'd get for the half-integer coefficients). Once you know it, you can easily figure out the coefficient at the next power in the same way and so on.
Now, if you also have a bound on $q$ you can plug in, it becomes interesting.
Oops, sorry for misunderstanding.
OK, you can easily do $Cd^M\log N$ then. The trick is that no matter how you split the d-dimensional simplex of volume 1 by a hyperplane through its center and no matter which piece you'll take, you'll be able to find a simplex of volume $1-d^{-m}$ conatining this piece where $m$ is some fixed number, which I will need some time to compute precisely (my educated guess would be m=4). Now just use this fact to obtain a simplex of either volume less than $N^{-2d}$ or with one vertex outside the ball of radius $N^{3d}$ containing the set of remaining polynomials after just $O(d^M\log N)$ steps. In both cases, you'll be able to find a linear dependence between the coefficients that is precise up to $N^{-2}$, which means that you can eliminate one coefficient from the polynomial entirely (the $d$-th power of the variable is still well below $N$, so the precision is enough to distinguish the integer values and each exactly attained equality which will not allow you to tell for sure which half you are in gives you food for interpolation).
Sorry if it is too sketchy. I'll try to edit it into something more reasonable later unless somebody gives a better solution.