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}.
$$