This comes down to finding the points mod p on a certain elliptic curve with complex multiplication by the Gaussian integers. The good news is that the error term in Hasse's theorem is entirely manageable, and the cases of small p can be dealt with pretty much by hand for p congruent to 1 mod 4. For some reason you are asking about p congruent to 3 mod 4. Which is basically easier.
The reduction to the counting problem goes like this: set up a character sum using the Legendre symbol, over residues mod p, of a summand with three factors, which will be zero unless the three conditions are all fulfilled (so [Legendre symbol of q minus 1] is one typical factor). Multiply out, and all the terms except the one counting those points on an elliptic curve (i.e. Sigma [Legendre symbol of cubic in q]) can be evaluated. The Sigma of quadratic terms are 1 or -1 by a standard sum (counts points on projective line).
Hope that helps. This problem looks eminently doable.
[Added: Since Robin has answered in a complementary way while I was typing, an amplification. If you do need p congruent to 1 mod 4 and calculations for small p, the key thing is the size of a and b when you write p as a sum of two squares.]
