Armin,

Let me try to solve your original problem differently.
First write the wanted polynomial in the form $f(x,y)=\sum_kx^kA_k(y)$ where
the leading polynomial $A_0(y)$ is not identically zero (otherwise we can
always replace $f(x,y)$ by $f(x,y)/x^\ell$ for a suitable $\ell$). Denote by $N$
the degree of the polynomial $A_0(y)$. For any prime $p>N!$ the numbers
$0$ and $(-1)^kk!$, where $k=0,\dots,N-1$, are distinct residues modulo $p$, 
so that $p!\equiv 0\pmod p$ and $(p-k)!=(p-1)!/\prod_{j=1}^{k-1}(p-j)\equiv(-1)^k(k-1)!^{-1}\pmod p$
are pairwise noncongruent modulo $p$ as well. Substituting $x=(2p-2k)!\equiv0\pmod p$ 
and $y=(p-k)!$ for each $k=0,1,\dots,N$ into $f(x,y)=0$ and reducing modulo $p$, we obtain
$N+1$ different solutions of the polynomial equation 
$A_0(x)\equiv0\pmod p$, so that all coefficients of $A_0(x)$ are divisible by $p$.
Since this is true for any prime $p>N!$, the polynomial $A_0(x)$ is identically zero,
which contradicts our assumption.

Is it elementary enough?