The combinatorial proof that $p \mid a^p - a$ when $p$ is prime is that $a^p - a$ counts the number of acyclic necklaces of length $p$ with $a$ colors. For any $n$, the cyclic group $\mathbb{Z}/n\mathbb{Z}$ acts by cyclic permutation on the set of necklaces of length $n$ with $a$ colors. When $p$ is prime, we can split up the set of necklaces as follows:
- The necklaces all of whose colors are the same, of which there are $a$, and
- The acyclic necklaces, of which there are $a^p - a$.
The action of $\mathbb{Z}/p\mathbb{Z}$ on the first collection is trivial and the action on the second is free because $\mathbb{Z}/p\mathbb{Z}$ has no nontrivial subgroups, so the action on the second collection splits up into $\frac{a^p - a}{p}$ orbits of size $p$ by the orbit-stabilizer theorem.
When $n$ is not prime, other orbit types may appear, since necklaces may have nontrivial cyclic structure such as $RBYRBY$, so there are orbits with nontrivial stabilizers. In this case the correct count of the number of acyclic necklaces (those on which $\mathbb{Z}/n\mathbb{Z}$ acts freely) is given, not by $a^n - a$, but by
$$\sum_{d \mid n}\; \mu(d) a^{n/d}$$
where $\mu$ is the Möbius function; the proof is a classical application of Möbius inversion and worth working out as an exercise. So the correct generalization to the non-prime case from the combinatorial point of view is that
$$n \mid \sum_{d \mid n}\; \mu(d) a^{n/d}.$$
In the specific case $a = 3, n = 4$, the group $\mathbb{Z}/4\mathbb{Z}$ has $\mathbb{Z}/2\mathbb{Z}$ as its only nontrivial subgroup. Letting the colors be $R, B, Y$, the orbits with full stabilizer look like $RRRR$, the orbits with stabilizer $\mathbb{Z}/2\mathbb{Z}$ look like $RBRB$, and the orbits with trivial stabilizer look like $RBYB$. There are $3$ of the first kind and
$$\frac{\mu(1) 3^4 + \mu(2) 3^2 + \mu(4) 3^1}{4} = \frac{3^4 - 3^2}{4} = 18$$
of the third kind, so $3$ of the second kind.