These are all the polynomials $f(x) \in \mathbb Z[x]$ satisfying two inequalities:

They had better actually give you probabilities, so $f(x) \in [0,1]$ for $x \in [0,1]$.

They are either totally deterministic or indeterministic, so either $f=0$, or $f=1$, or $f(x) \in (0,1)$ for $x \in (0,1)$.

Ignoring the $f=0$, $f=1$ case, this inequality plus the fact that $f$ is a polynomial implies that $f(x) \geq \epsilon x(1-x)$ for some $\epsilon$ and $1-f(x) \geq \epsilon x(1-x)$ for some $\epsilon$.

For the proof, note that for each $n$ greater than the degree of $f$, we may write $f$ uniquely as $$ \sum_{i=0}^n c_{i,n} x^i (1-x)^{n-i}$$ by choosing the $c_{i,n}$ in order to get the $i$th coefficient of $x$ right.

It is sufficient to show that for $n$ sufficiently large, $0 \leq c_{i,n} \leq \pmatrix { n \\ i}$.

In fact we will show that:

$$ c_{i,n} = \pmatrix { n \\ i} \left( f\left( \frac{i}{n}\right) + O\left( \frac{1}{n} \frac{i}{n} \left( 1- \frac{i}{n} \right) \right)\right)$$

or setting $x=i/n$, this looks a little more elegant as:

$$ c_{i,n} = \pmatrix { n \\ i} \left( f( x) + O\left( \frac{1}{n} x\left( 1- x \right) \right)\right)$$

Then choosing $n$ large enough that $O(1/n)< \epsilon$, we get the right bounds on $c_{i,n}$ and win.

Let $d$ be the degree of $f$. We can go from $c_{i,d}$ to $c_{i,n}$ by ignoring the last $n-d$ coin flips, which gives the formula

$$ c_{i,n} = \sum_{j=0}^d \pmatrix{ n-d \\ i-j}c_{j,d}$$

Now on the other hand we have:

$$ f(i/n) = \sum_{j=0}^d \left( \frac{i}{n} \right)^j \left( \frac{n-i}{n} \right)^{d-j} c_{j,d}$$

So it is sufficient to show that:

$$\pmatrix{ n-d \\ i-j} = \pmatrix { n \\ i} \left(\left( \frac{i}{n} \right)^j \left( \frac{n-i}{n} \right)^{d-j} + O\left( \frac{1}{n} \frac{i}{n} \left( 1- \frac{i}{n} \right) \right)\right)$$

or equivalently:

$$ \frac{ \pmatrix{ n-d \\ i-j} }{\pmatrix { n \\ i}} = \left( \frac{i}{n} \right)^j \left( \frac{n-i}{n} \right)^{d-j} + O\left( \frac{1}{n} \frac{i}{n} \left( 1- \frac{i}{n} \right) \right)$$

The left side is the probability of drawing $j$ white balls and then $d-j$ black balls from an urn with $i$ white balls and $n-i$ black balls, sampling without replacement. For the outcome in the two cases to be different, you have to draw the same ball twice, which happens $O(1/n)$ of the time, and then have it be a different color from the ball you would have gotten otherwise, which happens $O\left(\frac{i}{n} \left( 1- \frac{i}{n} \right) \right)$ of the time, which justifies the error term.

2more comments