A slight variation of your problem: counting real roots of polynomial systems using tools from algebraic geometry, is a problem that is very much studied in Nonlinear Algebra. This is an important question as many applications only care about real solutions. So yes, in fact, there is an "Ideal application" here (ha ha).
The short answer to "how hard is this problem" is "very," but there definitely exist tools and a wide range of work regarding this topic. A good reference might be, Real solutions to equations from geometry by Frank Sottile, which examines the univariate case in Chapter Two.
One can also think about dividing the real parameter space $(a_0, ... ,a_n)$ into regions with a certain number of real roots by exploiting the fact that the number of real roots changes when two complex roots come together (forming a multiple root). The value of the discriminant of a univariate polynomial encodes some of this information, since it is zero exactly when a univariate polynomial has a multiple root. When the degree is four or higher, the discriminant is positive if and only if the number of non-real roots is a multiple of four.
You wanted to avoid numerical solvers, but I will mention that numerical solvers such as Bertini exist for polynomial systems which take advantage of the polynomial structure to find roots (and thus classify them).
As for classifying roots in other quadrants of the complex plane, I'm not entirely sure, but it's a very interesting one. One might be able to take advantage of the work on counting real solutions. For example, if one appends the equation $x^2-y=0$, one can then ask how many real solutions in $y$ are there, giving the count of purely imaginary plus real solutions.