Let $q$ not be $2$. Diagonalize the form. If you can't, it's because you found your isotropic vector. Now take $ax^2+by^2+cz^2+dv^2$ where $a,b,c,d$ are coefficients, and then look at $ax^2+by^2$. Either it represents $0$ in which case we are done, or it represents $1$. $cz^2+dv^2$ either represents $0$ or it represents $-1$. In each case we are finished.

So now we've reduced to finding a solution to $ax^2+by^2=1$ or $ax^2+by^2=-1$ when one exists. It's enough to solve the homogenization $ax^2+by^2=z^2$ with a nonzero $z$ and divide, and I think this is efficiently done by randomization.

See the preprint https://arxiv.org/abs/1404.0281. I have just implemented this a month ago, and would be happy to share the code.