A combinatorial proof for the identity $\sum_i \sum_j \min(i,j) = \sum_k k^2$

You could try a recursion. If $L(n)$ is the left side, what is $L(n+1) - L(n)$?

Your observation makes a nice "proof without words", though.

You could visualize it like this. Start with an $n \times n$ square divided into $n^2$ unit squares. Label the rows and the columns $1$ through $n$. Now imagine that you have a bunch of cubical blocks one unit on a side. On the unit square in row $i$, column $j$ you stack $\min\{i,j\}$ of these blocks. Clearly this requires $\sum_{i=1}^n \sum_{j=1}^n \min\{i,j\}$ blocks.

To get the other side of the identity, count the blocks by layers. There are clearly $n^2$ blocks in layer one, at the bottom. The column of blocks in row $i$, column $j$ reaches up to layer $k$ if and only if $k \le \min\{i,j\}$, which is true if and only if $k \le i$ and $k \le j$, i.e., $i,j \ge k$. The number of cells in the original grid satisfying $i,j \ge k$ is $[n-(k-1)]^2$ so counting by layers gives a total of $$\sum\limits_{k=1}^n [n-(k-1)]^2 = \sum\limits_{k=0}^{n-1} (n-k)^2 = \sum\limits_{k=1}^n k^2$$ blocks.