My favorite elementary proof is the second one given by Gauss, based on his construction of geodesic polar coordinates $(r,\theta)$. Below is a sketch - you have to fill in the details yourself. I guess it's a bit too late for you to use in your course, but maybe someone else will find it useful.
To construct geodesic polar coordinates, we pick an arbitrary point $P$ on the surface, and a tangent vector $\vec{v}$ based at $P$. For any sufficiently nearby point $Q$, there is a unique shortest geodesic segment $PQ$. Let $r(Q)$ be the length of this segment, and let $\theta(Q)$ be the angle its initial velocity makes with the vector $\vec{v}$.
Using your favorite method of deriving the geodesic equations, you can prove Gauss' lemma: the curves of constant $r$ (the "geodesic circles") are perpendicular to the curves of constant $\theta$ (the "radial geodesics"). Thus in coordinates $(r,\theta)$ the line element of the surface takes the form
$$ds^2 = dr^2 + \rho^2 d\theta^2,$$
for some function $\rho = \rho(r,\theta)$, and the area element takes the form
$$ dA = \rho dr d\theta. $$
For geometric reasons, the function $\rho$ must satisfy
$$ \rho(0,\theta) = 0 \\ \rho_r(0,\theta) = 1 $$
or equivalently,
$$\rho = r + O(r^2).$$
You can use your favorite proof of the Theorem Egregium to show that the Gaussian curvature is given by:
$$ K(r,\theta) = \frac{-\rho_{rr}(r,\theta)}{\rho(r,\theta)}. $$
Now say $QR$ is a geodesic segment which is completely contained in the coordinate patch constructed above, with a parameterization of the form $(r(\theta),\theta)$. If $\phi = \phi(\theta)$ denotes the angle that this curve makes with the radial geodesics, then using your favorite method of writing down the geodesic equations, you can show that
$$ \phi'(\theta) = - \rho_r(r(\theta),\theta). $$
Therefore, the total curvature of the geodesic triangle $T = \Delta PQR$ is given by
$$ \begin{eqnarray*} \iint_{T} KdA &=& - \iint_{T} \rho_{rr} dr d\theta \\
&=& \int_{PQ} \left[ \rho_r(0,\theta) - \rho_r(r(\theta),\theta) \right] d\theta \\
&=& \int_{PQ} \left[ 1 - \phi'(\theta) \right] d\theta \\
&=& \alpha + \left( \beta - (\pi - \gamma) \right), \\
&=& \alpha + \beta + \gamma - \pi \end{eqnarray*}$$
where $\alpha, \beta, \gamma$ are the internal angles of the triangle.
Of course, the last step is Stokes' theorem in disguise. Basically, by choosing a very nice parameterization of the triangle, we get away with using only the fundamental theorem of calculus.
This proof is given by Gauss in his "General Investigations of Curved Surfaces", sections 19-20.