Gibbs' inequality

Start from the elementary inequality $\ln x \le x - 1$ for all $x > 0$, with equality only at $x=1$ (this follows since $f(x) = \ln x - (x-1)$ has $f(1)=0$, $f'(x) = 1/x - 1$, which is positive for $x<1$ and negative for $x>1$, so $f$ has a unique maximum at $x=1$). Dividing by $\ln 2$ gives $\log_2 x \le (x-1)/\ln 2$.

Apply this with $x = q_i/p_i$ for each $i$: $\log_2(q_i/p_i) \le (q_i/p_i - 1)/\ln 2$. Multiply both sides by $p_i > 0$ (which does not flip the inequality) and sum over $i$: $\sum_i p_i \log_2(q_i/p_i) \le \frac{1}{\ln 2}\sum_i (q_i - p_i) = \frac{1}{\ln 2}\left(\sum_i q_i - \sum_i p_i\right) = \frac{1}{\ln 2}(1 - 1) = 0$, since both $p$ and $q$ are probability distributions summing to $1$.

The left side is exactly $-D(p\|q)$ (note the sign flip from $q_i/p_i$ versus $p_i/q_i$ inside the log), so this proves $D(p\|q) \ge 0$.

Equality throughout requires equality in $\ln x \le x-1$ for every $i$ with $p_i > 0$, which happens only when $q_i/p_i = 1$ for every such $i$, i.e. $p = q$.