View the vertices as elements of $\mathbb{Z}^n$. If $a\in\mathbb{Z}^n$, define a function $f_a$ on the vertices by
$$
  f_a(x) = (-1)^{a^Tx}.
$$
This function is an eigenvectors and if $a$ has weight $w$, the eigenvalue is $n-2w$. I can make this look more combinatorial by viewing vertices (and $a$) as subsets of $\{1,\ldots,n\}$ and noting that $f_a(x)$ is determined by the parity of $a \cap x$ (abusing notation).
Different choices of $a$ give linearly independent eigenvectors, so we get the multiplicities as well as the eigenvalues.

The actual difficulty with this question is in deciding what you mean by a "graph 
theoretical proof". From where I write, linear algebra is a standard and fundamental tool in graph theory.

Comment response: (too long for a comment box). OK. The $n$-cube is the Cartesian product of $n$ copies of $K_2$.
The eigenvalues of the Cartesian product of two graphs $G$ and $H$ are the sums of the eigenvalues of $G$ with the eigenvalues of $H$. (The simplest way to see this is to note that the eigenvectors of the product are the Kronecker products of the eigenvectors of the factors.) Applying this $n$ times to $K_2$ gives the desired result.

There are formulas for the effect on the characteristic polynomial adding edges or vertices, but they are not all simple, and I cannot see how to use them to get the eigenvalues of the $n$-cube.