Why aren't all matrices diagonalisable?

The difference is that diagonalization requires that you make the same change of variables in the domain and in the codomain. On the other, making "elementary row and column operations" can be interpreted as changing the basis in only one of these spaces.

A representative example of a non-diagonalizable matrix would be just

$$A := \begin{pmatrix}0 & 1 \\ 0 & 0 \end{pmatrix}$$

If you understand this example, then in principal you essentially understand the general case -- see the Jordan canonical form.

Play around with it and see if you can get a feel for it. Here's one thing to notice: if you let

$$v := \begin{pmatrix} 0 \\ 1 \end{pmatrix}$$

then $A v \neq 0$ but $A^2 v = 0$. Could a diagonal matrix do something like that to a vector?

Yes, you are making a mistake. A matrix $A$ being diagonalizable means that you can find an invertible matrix $S$ so that $SAS^{-1} = D$, for $D$ a diagonal matrix. We say that we conjugate $A$ by $S$ to get $D$. The geometric intuition here is that conjugation amounts to writing the matrix $A$ in a different basis (meaning that now we ask to express $A e_i$ in terms of the same basis $e_i$). The row and column operations you describe amount to changing basis twice, once on the domain side, and once on the co-domain side (meaning we are expressing $A e_i$ in terms of a different basis $f_i$). (As Jonas just posted.)

Here are some exercises:

1. Show that row operations can be achieved by multiplying by an elementary matrix on the left. Show that column operations can be achieved by multiplication by an elementary matrix on the right.
2. Show that the matrix $[[1, i],[i,-1]]$ is not diagonalizable. (Hint: What must the eigenvalues be?)

It is also not true that all matrices are upper triangulazable - this is only true over $\mathbb{C}$. (Or other algebraically closed field. You need to guarantee the existence of an eigenvector, so you need to be able to solve polynomial equations. As a counter-example, you can take the rotation by 120 degrees matrix on $R^2$.)