This comment serves to record a partial attempt, which didn't get very far but might be useful to others. Following a suggestion of Mark Wildon and Arthur B, define
$$f_n(\alpha) := \sum (-1)^r \binom{n}{r}^{\alpha}.$$
This is zero for $n$ odd, so we will assume $n$ is even from now on.

Mark Wildon shows that it would be enough to show that $f_n(1/2) \geq 0$ for all $n$. 
It is easy to see that $f_n(0) = 1$ and $f_n(1)=0$. Arthur B notes that, experimentally, $f_n(\alpha)$ appears to be decreasing on the interval $[0,1]$. If we could prove that $f_n$ was decreasing, that would of course show that $f_n(1/2) > f_n(1) =0$.

I had the idea to break this problem into two parts, each of which appears supported by numerical data:  
1. Show that $f_n$ is convex on $[0,1]$.  
2. Show that $f'_n(1) < 0$.  
If we establish both of these, then clearly $f_n$ is decreasing.

I have made no progress on part 1, but here is most of a proof for part 2. We have
$$f'_n(1) = \sum (-1)^r \binom{n}{r} \log \binom{n}{r} = \sum (-1)^r \binom{n}{r} \left( \log(n!) - \log r!- \log (n-r)! \right)$$
$$=-2 \sum (-1)^r \binom{n}{r} \left( \log(1) + \log(2) + \cdots + \log (r) \right)$$ $$=-2 \sum (-1)^r \binom{n-1}{r} \log r.$$
At the first line break, we combined the $r!$ and the $(n-r)!$ terms (using that $n$ is even); at the second, we took partial differences once.

This last sum is evaluated asymptotically in this [math.SE thread][1]. The leading term is $\log \log n$, so the sum is positive for $n$ large, and $f'_n$ is negative, as desired. The sole gap in this argument is that the math.SE thread doesn't give explicit bounds, so this proof might only be right for large enough $n$.

This answer becomes much more interesting if someone can crack that convexity claim.


  [1]: http://math.stackexchange.com/questions/64971/proof-sum-limits-k-1n-binomnk-1k-log-k-log-log-n-gamma-fr