There's a very pretty combinatorial proof of the general identity $$\sum_{k \geq 0} \binom{n}{rk} = \frac{1}{r} \sum_{j=0}^{r-1} (1+\omega^j)^n,$$
for $\omega$ a primitive $r$th root of unity, in Benjamin, Chen, and Kindred, "Sums of Evenly Spaced Binomial Coefficients," Mathematics Magazine 83 (5), pp. 370-373, December 2010.
They show that both sides count the number of closed $n$-walks on $C_r$ beginning at vertex 0, where $C_r$ is the directed cycle on $r$ elements with the addition of a loop at each vertex, and a walk is closed if it ends where it starts.
Left-hand side: In order for an $n$-walk to be closed, it has to take $kr$ forward moves and $n-kr$ stationary moves for some $k$.
Right-hand side: The number of closed walks starting at vertex $j$ is the same regardless of the choice of $j$, and so it suffices to prove that the total number of closed $n$-walks on $C_r$ is $\sum_{j=0}^{r-1} (1+\omega^j)^n.$ For each $n$-walk with initial vertex $j$, assign each forward step a weight of $\omega^j$ and each stationary step a weight of $1$. Define the weight of an $n$-walk itself to be the product of the weights of the steps in the walk. Thus the sum of the weights of all $n$-walks starting at $j$ is $(1+\omega^j)^n$, and $\sum_{j=0}^{r-1} (1+\omega^j)^n$ gives the total weight of all $n$-walks on $C_r$. The open $n$-walks can then be partitioned into orbits such that the sum of the weights of the walks in each orbit is $0$. Thus the open $n$-walks contribute a total of $0$ to the sum $\sum_{j=0}^{r-1} (1+\omega^j)^n$. Since a closed $n$-walk has weight $1$, $\sum_{j=0}^{r-1} (1+\omega^j)^n$ must therefore give the number of closed $n$-walks on $C_r$.
They then make a slight modification of the argument above to give a combinatorial proof of
$$\sum_{k \geq 0} \binom{n}{a+rk} = \frac{1}{r} \sum_{j=0}^{r-1} \omega^{-ja}(1+\omega^j)^n,$$
where $0 \leq a < r$.
Benjamin and Scott, in "Third and Fourth Binomial Coefficients" (Fibonacci Quarterly, 49 (2), pp. 99-101, May 2011) give different combinatorial arguments for the specific cases you're asking about, $\sum_{k \geq 0} \binom{n}{3k}$ and $\sum_{k \geq 0} \binom{n}{4k}$. I prefer the more general argument above, though, so I'll just leave this one as a link and not summarize it.
The keyword is discrete Fourier transform. The basic lemma is that if $\zeta_k$ is a primitive $k^{th}$ root of unity then
$$\sum_{i=0}^{k-1} \zeta_k^{ij} = \begin{cases} 0 \text{ if } k \nmid j \\ k \text{ otherwise}. \end{cases}$$
It follows that if $f(x) = \sum a_i x^i$ is a formal power series then the sum of every $k^{th}$ term of $f$ is
$$\sum a_{ki} x^{ki} = \frac{1}{k} \sum_{i=0}^{k-1} f(\zeta_k^i x).$$
In this particular case we have, for example,
$$\sum {n \choose 2i} = \frac{1}{2} \left( (1 + 1)^n + (1 - 1)^n \right) = 2^{n-1}$$
and
$$\sum {n \choose 3i} = \frac{1}{3} \left( (1 + 1)^n + (1 + \omega)^n + (1 + \omega^2)^n \right) = \frac{2^n + (-\omega^2)^n + (-\omega)^n}{3}$$
where $\omega$ is a primitive third root of unity (and we used the fact that $1 + \omega + \omega^2 = 0$). The answer is messier in general.
Best Answer
Actually the above method works for all numbers, not only primes. In your case for $n=4$, at the squares you get $1+(-1)+1+(-1)$.
This lemma will help you:
Lemma Let $\omega_1,..,\omega_{\ell}$ be all $\ell$-th root of unity. Then
$$ \sum_{i=1}^l \omega_i^k = \left\{ \begin{array}{l c} 0 & \mbox{ if l doesn't divide k} \\ l & \mbox{ if l divides k} \\ \end{array} \right. $$
Proof: Second is trivial. For First, pick some $\omega$ primitive root and observe that
$$\sum_{i=1}^l \omega_i^k = \sum_{i=1}^l \omega_i^k \omega^k$$
Thus
$$(1-\omega^k)\sum_{i=1}^l \omega_i^k =0$$
P.S. The same method can also be used to calculate $$\sum_{m=0}^{\lfloor\frac{n}{k}\rfloor}{n\choose km+r}$$ for $0 \leq r < k$. To do this, you simply add
$$\omega_i^{-r} (1+\omega_i)^n$$