If Q(X) has only integer roots then, trivially, any prime number bigger than the product of roots works.

Replace Z_p by GF(q) and it becomes trivial.

By  Z_[p}  I  mean integer mod  p, so the same as GF(p). But why the question is trivial in this case?

If you allow GF(q) with q a power than you can always climb in an extension of degree high enough of Z_p for any p. If you only want prime fields then it is more difficult. Already for Q a quadratic you want the discriminant to be a quadratic residue mod p.

If Q is a cyclotomic polynomial a divisor of x^n-1 for some n, it is easy. Just take a p such that n divides p-1. For a general Q I do not know. Maybe you need to understand the Galois group of the number field defined by Q.

I see it in the following way. Consider a polynomial P(X) with coefficients in Z. Suppose that P has n different solutions in C (every one with multiplicity 1). Then the sentence Ex1,  ... xn (x1 \neq x2 /\ .... /\ x[n-1] \neq xn) /\ P(x1, ..., xn) = 0, which is purely existential,  is true in C. Being a purely existential sentence that contains no constants, this is true in all algebraically closed fields of finite characteristic, with EXCEPTION for finitely many primes. (this happens more generally for AE-sentences, not only for E-sentences). But the smallest a.c. field of characteristic p is the union of GF(p^m) over all m. So the polynomial has n different solutions in such a GF(p^m) for all but finitely many primes. The same happens also if P has some solutions with non-trivial multiplicities 

The original question is more difficult because it is about the fields GF(p) only. However, one can consider a non-trivial ultrapower F = prod(GF(p)) / U, where U is a non-principal ultrafilter in the set of subsets of P where P is the set of primes. F is a field of characteristic 0 which is not algebraically closed and so called pseudo-finite. Those fields have been extensively studied by James Ax.

https://en.wikipedia.org/wiki/Pseudo-finite_field

So the situation is as follows: if the algebraic numbers in F are not all algebraic numbers, (which is very likely) then a minimal polynomial of such algebraic number has strictly less than n solutions in all BUT finitely many GF(p). Unhappily I have no the time to see how the situation exactly looks like. I recommend the paper:

Ax, James (1968), "The Elementary Theory of Finite Fields", Annals of Mathematics, Second Series (Annals of Mathematics) 88 (2): 239–271, doi:10.2307/1970573, ISSN 0003-486X, MR 0229613, Zbl 0195.05701

and the book:

Fried, Michael D.; Jarden, Moshe (2008), Field arithmetic, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge 11 (3rd revised ed.), Springer-Verlag, pp. 448–453, ISBN 978-3-540-77269-9, Zbl 1145.12001

Better news. The article:

http://www.sciencedirect.com/science/article/pii/S0168007297000171

by Zoe Chatzidakis if freely downloadable. At page 99 it is proven that there is a decision procedure if some sentence is true in all Z/pZ or not (without powers p^m!), and there they show also how to compute the exceptional primes for general formal sentences. It is this way which should be followed!

Dear Mihai, maybe you should explain the interaction between model theory and number theory. The context is not obvious.

Dear Mihai, Thank you very much  for your answers and very helpfull links Please see also  the following link.

http://math.stackexchange.com/questions/1667471/does-any-polynomial-with-integer-coefficients-split-over-some-prime-field

I thank all others for their attention to my question.

@Peter Breuer: Dedekind says that if the mod $p$ reduction of $F(x)$ is separable, then the degrees of the irreducible factors over $\mathbb F_p$ are the cycle lengths of an element $g$ of the Galois group of $F(x)$ over $\mathbb Q$. As this Galois group is (by construction) regular, a fixed point of $g$ implies that $g$ fixes all roots.  

P.S.: I consider research gate kind of spammy. Such discussions as here have a better place at  http://math.stackexchange.com/.

@ Peter Breuer: for fixed p, the union of all GF(p^n) is the algebraic closure of GF(p). It is union because GF(p^a) \subset GF(p^b) iff a | b. So it is enough to make union of GF(p^{n!}) with p fixed, because this is an ascending chain of fields.

@ Patrick Sole: There is no special connection between model-theory and number theory. It is just that model theory speaks sometimes about the truth of some existential sentences. Over domains, such sentences are equivalent with the solvability of some equations. In lucky cases model-theory has transfer theorems which can be applied, in most cases in an uneffective way (just non-constructive proofs of existence).

@ Peter Müller: Thank you very much for the nice solution in the other discussion track. The connection with the work by James Ax and other model-theorists is exactly Chebotarev's density theorem. But the solution displayed, which avoids this, is nicer.

@Ali Taghavi: Very interesting question indeed.