I think you are right and you are on the right track. Lets look at degree two polynomials and above. Let be a polynomial of degree . Let the smallest positive real root be and the largest positive real root be . In the range you get a lot of swerving around and it'll be difficult to find the distribution of natural numbers that it hits in that area.
Now lets focus our attention on the values of the polynomial beyond the biggest root. Since the coefficients are natural numbers we must have that the polynomial will be positive after that last root. From here on lets examine the interval where . We need that the polynomial misses infinitely many natural numbers. So if , then we the polynomial misses one number in that range. Since the range was arbitrary with , we must have that for every such range we are missing at least one natural number. Since there are infinitely many of these intervals, we are missing infinitely many numbers.
The key step will be to show that (or if yo u prefer a tighter bound). You can either do it directly or you can represent the polynomial in a clever way to make it easier for yourself.
Now if , we surely get that the polynomial misses infinitely many natural numbers. The only posibility left is to consider a polynomial for natural numbers a and b and see when it misses inf. many points and when it does not. It should be pretty straightforward.