Let $p(x)$ be a fixed monic polynomial with integer coefficients and degree $d$. If $r$ is one of its roots and $r^n = b$ is real and non-negative (and $n$ is minimal with this property), then $b$ is a product of algebraic integers, hence an algebraic integer. We therefore have $r = \zeta_n \sqrt[n]{b}$
for some primitive $n^{th}$ root of unity $\zeta_n$. Since $\sqrt[n]{b}$ is real, $\bar{r} = \zeta_n^{-1} \sqrt[n]{b}$ is also a root of $p$, and so it follows that $\frac{r}{\bar{r}} = \zeta_n^2$
lies in the splitting field $F$ of $p$. But $\zeta_n^2$ generates a cyclotomic field of degree $\varphi \left( \frac{n}{\gcd(2, n)} \right)$, and so this must divide the degree of $F$, which divides $d!$. It is known that there are only finitely many numbers with a given totient, so there are only finitely many possibilities for $n$, and so for fixed $p$ this indeed reduces to a finite problem as Gerry says.
When $p(x) = x^4 - x^3 - x^2 - x - 1$, we compute that $\bmod 2$ we have $p(x) \equiv \frac{x^5 - 1}{x - 1}$, which is irreducible (the smallest finite field over $\mathbb{F}_2$ which has elements of order $5$ is $\mathbb{F}_{2^4}$), so $p$ is irreducible and its splitting field has degree dividing $4! = 24$. So $\zeta_n^2$ lies in its splitting field only if $\varphi \left( \frac{n}{\gcd(2, n)} \right) | 24.$
If $q$ is a prime dividing $n$, then $q - 1 | 24$, so we can only have $q = 2, 3, 5, 7, 13$. Of these, the only odd prime which also divides $24$ is $3$ and it only does so once, so $3$ can occur with multiplicity at most $2$ and the other odd primes occur with multiplicity at most $1$. Since $2^3 | 24$, the prime $2$ occurs with multiplicity at most $5$.
Summarizing, to prove that $p(x)$ does not have a root which is the root of a real number, it suffices to prove that $r^{2^5 \cdot 3^2 \cdot 5 \cdot 7 \cdot 13}$ is not real for any of the roots $r$, and this can be done by a finite calculation. Of course this is a large exponent, and the actual size of the possible values of $n$ is smaller, but the possible values of $n$ are somewhat tedious to list out.
Here's another idea for ruling out values of $n$. Recall that if $K \subset L$ is an inclusion of number fields, then the discriminant $\Delta_K$ of $K$ divides $\Delta_L$. The discriminants of the cyclotomic fields $\mathbb{Q}(\zeta_n)$ are known (see Wikipedia, although the general formula is somewhat complicated), and in particular every odd prime divisor of $n$ divides them, so by computing the discriminant of $p$ we can rule out some prime factors.
WolframAlpha tells me that the discriminant of $x^4 - x^3 - x^2 - x - 1$ is $-563$. This is prime so it must be the discriminant of the splitting field, and this already rules out all of the possible values of $n$ above.