$\def\ZZ{\mathbb{Z}}$I answered a similar question over on math.SE. Some general thoughts:
All proofs I know rely on constructing an element of the group ring which acts by $|G|/\dim V$, or some closely related quantity, on $V$. Since $G$ acts on the regular rep by matrices in $GL_n(\ZZ)$, and $V$ is a summand of the regular rep, this shows that $|G|/\dim V$ is an integer. (Exactly how easy that argument is depends how much algebra your audience has.)
Most books seem to use $\sum_{\chi} \sum_{g \in G} \chi(g) g$, where the sum is over the irreducible characters of $\chi$. This acts by $|G|/\dim V$ on $V$, and clearly lies in $\ZZ^{alg}[G]$, where $\ZZ^{alg}$ is the ring of algebraic integers.
In fact, setting $a_g = \sum_{\chi} \chi(g)$, the $a_g$ are integers, so this element is in $\ZZ[G]$. I spent some time a few months ago trying to find a combinatorial proof that the $a_g$ are integers, without developing the theory of algebraic integers, but failed. For a while I believed that $a_g \geq 0$, but that turned out to be false. Let $X \subset \mathbb{F}_2^5$ be the subgroup $\{ (x_1, x_2, x_3, x_4, x_5) : x_1+x_2+x_3+x_4+x_5=0 \}$ and let $x = A_5 \ltimes X$. If I recall correctly (my notes are at home), I got that $a_g$ is negative at $((12)(34),\ (1,0,0,0,1) )$.
An alternative hack is to use the element $\sum_{g, h \in G} ghg^{-1} h^{-1}$. This is manifestly in $\ZZ[G]$ and it acts by $(|G|/\dim V)^2$ on $V$. That let's you avoid mentioning algebraic integers, but it still involves character theory computations that I find unenlightening.
I'd be interested in hearing other proofs!