Start with the matrix $$ M' = \begin{bmatrix} 0 & 0 & & & \\ 0 & a_2 & b_2 & & & \\ & & \ddots & & \\ & & b_{n-2} & a_{n-1} & 0 \\ & & & 0 & 0 \end{bmatrix}, $$ i.e. your matrix $M$ but with the two entries on the edges deleted. This is a symmetric tridiagonal matrix, so it can be diagonalized in $O(n^2)$ and has $n$ real eigenvalues. You can easily check that $M$ and $M'$ have the same eigenvalues ($tI-M$ can be transformed to $tI-M'$ with two elementary row operations). Adding back each deleted entry is a nonsymmetric rank-one perturbation, so you can use the nonsymmetric version of the Bunch-Nielsen-Sorensen formula twice to compute the diagonalization of $M$ from that of $M'$ in $O(n^2)$.
As to the question of whether the eigenvalues are nonpositive, here is a counterexample: $$ \begin{bmatrix} 0 & 0 & 0 & 0 \\ 2 & -1 & 2 & 0 \\ 0 & 2 & -1 & 2 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}. $$