We may identify $V$ with the field $\mathbb{F}_p$ of size $p$, then denoting $g_k(x):=g(x+k)$ for $k\in \mathbb{F}_p$ the questions reads as:
if $f(x)\not\equiv g_k(x)$ for each $k\in \mathbb{F}_p$, prove that there exists $h(x)$ such that $h(x)\ne f(x)$ for all $x$; but for each $k$ there exists $x(k)$ for which $h(x(k))=g_k(x(k))$.
If $g\equiv c$ is a constant coloring, we find a vertex $v\in \mathbb{F}_p$ for which $f(v)\ne c$ and put $h(v)=c$, and put $h(x)\in C\setminus \{f(x)\}$ for $v\ne x$ arbitrarily (this is possible since $|C|\geqslant |\{c,f(v)\}|=2$.)
If $g$ is not constant, we additionally require that $x(k)\colon \mathbb{F}_p\to \mathbb{F}_p$ is a bijection. Then we need $f(x(k))\ne g_k(x(k))$ for all $k$ (and $h$ is automatically defined by $h(x(k))=g_k(x(k))$). Consider the $p\times p$ matrix with both rows and columns indexed by $\mathbb{F}_p$ and put a star at the entry $(x,k)$ iff $f(x)\ne g(x+k)$. We want $p$ non-attacking rooks on the starred entries. Assume the contrary, then by Hall lemma (or Koenig theorem if you prefer) there exist sets $A,B\subset \mathbb{F}_p$ such that $|A|+|B|=p+1$ and $f(x)=g(x+k)$ for $x\in A$, $k\in B$.
If $|B|=1$, then $|A|=\mathbb{F}_p$ and $f(x)=g(x+k)$ for all $x$ where $B=\{k\}$. This contradicts to our assumption.
If $|A|=1$, then $B=\mathbb{F}_p$ and we get that $g$ is constant, which also is not the case.
So, assume hereafter that $1<|A|,|B|<p$. Then we may also assume without loss of generality that $g$ takes colors from the set $\mathbb{F}_p$. Replacing $f(x)$ to 0 for $x\notin A$, we get the same for $f$, and $f(x)=g(x+k)$ for $x\in A$, $k\in B$ still holds. Now the functions $f,g\colon \mathbb{F}_p\to \mathbb{F}_p$ are given by polynomials of degree at most $p-1$. Denote degree of $g$ by $d$, we have $d\geqslant 1$ since $g$ is not constant. Then we may write $d=d_1+d_2$ where $0\leqslant d_1<|A|$, $1\leqslant d_2<|B|$. Then the coefficient of $x^{d_1}k^{d_2}$ in the polynomial $h(x,k):=g(x+k)-f(x)$ is non-zero (it equals to a leading coefficient of $g$ times some non-zero binomial coefficient.) Any other monomial $x^a k^b$ in $h$ has either $a<d_1$ or $k<d_2$ (or both). Thus by generalized Combinatorial Nullstellensatz there exist $x\in A$, $k\in B$ with $h(x,k)\ne 0$, a contradiction.
Generalized Combinatorial Nullstellensatz is the following slight generalization of Alon's Combinatorial Nullstellensatz:
whenever $f(x_1,\ldots,x_k)$ is a polynomial with coefficients in the field $K$, the coefficient of the monomial $\prod x_i^{d_i}$ in $f$ is non-zero, and for each other monomial $\prod x_i^{c_i}$ in $f$ there exists at least one index $j$ such that $c_i<d_i$, then for arbitrary sets $A_i\subset K$ for which $|A_i|>d_i$ there exist $a_i\in A_i$ such that $f(a_1,\ldots,a_k)\ne 0$.
