Example: $Q(x) = x^{p-2} - 1$. For any $i < j < p$:
$$Q(j) - Q(i) = y^{p-2} - x^{p-2} \equiv \frac{1}{y} - \frac{1}{x} \pmod{p},$$
which clearly isn't divisible by $p$, and
$$jQ(j) - iQ(i) = (y^{p-1} - x^{p-1}) - (y - x) \equiv (x - y) \pmod{p}$$
also isn't divisible by $p$.

Suppose that there exists such a polynomial of smaller degree. It follows from the statement that all of $Q(1), Q(2), \dots, Q(p-1)$ give different remainders modulo $p$, and also $1Q(1), 2Q(2), \dots, (p-1)Q(p-1)$ give different remainders modulo $p$. Let's use the following fact: $1^k + 2^k + \dots + (p-1)^k \equiv 0 \pmod{p}$ for any $k$ from $1$ to $p-2$. Then consider $1Q(1) + 2Q(2) + \dots + (p-1)Q(p-1)$. From the fact above, this number is $0$ modulo $p$ (as each degree in the polynomial $xQ(x)$ is in the range $[1, p-2]$). Suppose that among the numbers $1P(1), \dots, (p-1)P(p-1)$ there are all remainders modulo $p$, except for $x$. Then:
$$0 \equiv 0 + 1 + \dots + (p-1) \equiv 1Q(1) + 2Q(2) + \dots + (p-1)Q(p-1) + x \equiv x \pmod{p},$$
so $1Q(1), 2Q(2), \dots, (p-1)Q(p-1)$ modulo $p$ give remainders $1, 2, \dots, p-1$ in some order. Then none of $Q(1), Q(2), \dots, Q(p-1)$ is divisible by $p$, and they also give remainders $1, 2, \dots, p-1$ in some order.
But then:
$$(p-1)! \equiv 1Q(1) \times 2Q(2) \times \dots \times (p-1)Q(p-1) \equiv (p-1)!^2 \pmod{p},$$
which, by the Wilson theorem, gives, $-1 \equiv 1 \pmod{p}$, this contradiction completes the proof.