Didn't Lenstra, Lenstra and Lovász in their famous LLL paper prove that factorization of polynomials over $\mathbb Q$ can be done in polynomial time? You get a rational root if and only if there is a factor of degree 1, and the polynomial has only rational roots if and only if all factors have degree 1.
Lenstra, A.K.; Lenstra, H.W.jun.; Lovász, László:
Factoring polynomials with rational coefficients. (English)
Math. Ann. 261, 515-534 (1982).
At least in principle, a solution is provided by the following result due to J. Sylvester:
Theorem (Sylvester). For each natural number $n \geq 2$ there exists a set of at most $n-1$ polynomials with integer coefficients $$R_{n, \, 1}(X_1, \ldots, X_n), \ldots, R_{n, \, k(n)}(X_1, \ldots, X_n)$$
such that the monic real polynomials of degree $n$ $$P(x)=x^n+a_{1}x^{n-1}+ \cdots + a_n$$
having only real roots are precisely those for which $$R_{n, \, 1}(a_1, \ldots, a_n) \geq 0, \ldots, R_{n, \, k(n)}(a_1, \ldots, a_n) \geq 0.$$
This can be seen as a generalization of the well-known fact that a real quadratic monic polynomial $x^2+a_1x+a_2$ has only real roots if and only if its discriminant $$D_2(1, \, a_1, \, a_2)=a_1^2-4 a_2$$
is non-negative. In fact, for all positive integers $n$ we have $$R_{n, \, 1}(a_1, \ldots, a_n) = D_n(1, \, a_1, \ldots, a_n),$$
where $D_n$ is the discriminant of $P(x)$, whereas the other polynomials $R_{n, \,i}$ can be explicitly computed in terms of determinants extracted from the Sylvester matrix of $P$ and $P'$.
So, in order to answer your question, one must check whether $$R_{n, \, 1}(\epsilon_1 a_1, \ldots, \epsilon_n a_n) \geq 0, \ldots, R_{n, \, k(n)}(\epsilon_1 a_1, \ldots, \epsilon_n a_n) \geq 0$$
for some choice of $\epsilon_1, \ldots, \epsilon_n \in \{-1, \, 1 \}.$ From the computational point of view, the problem is that the number of non-zero coefficients in our polynomials rapidly increases with the degree: for instance, $R_{9, \,1}=D_9$ has $26095$ terms.
For further details, see
C. Niculescu, L. E.Persson: Convex Functions and their Applications: A Contemporary Approach, Appendix B.
Best Answer
There is indeed an easy way to check if a univariate poly with real coefficients has a real root, without computing the roots.
Note that the answer for odd degree polynomials is always yes. For an even degree polynomial $p(x)$ do the following:
Compute the Hermite form of the polynomial. This is a symmetric matrix defined e.g. here: (on page 4, near the bottom denoted by $H_1(p)$). The entries of this matrix can be filled using Newton identities.
The number of real roots of $p(x)$ is equal to the signature of the Hermite matrix $H_1(p)$, i.e., the number of positive eigenvalues minus the number of negative eigenvalues.
Since the Hermite form is symmetric, its characteristic poly has only real roots. Therefore, we can apply Descartes' rule of signs to its char. polynomial, which would give us exactly the number of positive and negative eigenvalues of the Hermite form.
This process gives you the exact number of real roots of $p(x)$ without computing the roots, and in particular you can see if the polynomial has a real root.
Hope this helps.
-Amirali Ahmadi