Here is an example of a nice problem for which no combinatorial proof seems to be known. It is related to a problem studied in this paper https://arxiv.org/abs/1612.08698
Let $G$ be a $d$-degenerate graph (i.e. each subgraph contains a vertex of degree at most $d$). A classical result in graph theory is that if each vertex is given a list of $d+1$ colors, then every vertex can choose a color from its list such that the resulting coloring is proper.
Now, assume instead that each vertex of $G$ is given a list of size $d+1$ colors, except one vertex which has a list of size $d$. It can be proved with the combinatorial nullstellensatz that in this case again, each vertex can be colored with a color from its list, such that the resulting coloring of $G$ is proper (see the paper above, where a stronger result is proved when $d+1$ is prime, but the proof actually works in the weaker setting for general $d$).
I have worked on finding a combinatorial proof of this result, and I know several other researchers in the area who have studied this problem, without success.