Indeed, as you note, the decomposition is not unique, and there is no requirement that the components be orthogonal. However, you should treat the non-uniqueness as a good thing, because all you need to do is exhibit one decomposition that works, and you are not required to characterise all the possible decompositions. Because all you need to do is show one example, you can impose any additional requirements on your example that you find convenient, with orthogonality being the obvious go-go.
In practice, then, it is enough to just diagonalize the matrix.
That said, the diagonalization does seem to give you some awkward-looking vectors, i.e. it tells you to decompose as
\begin{align}
\rho
&=
\frac{3+\sqrt{5}}{8}
\frac{1}{1+\varphi^2}
\begin{pmatrix}\varphi\\0\\1\end{pmatrix}\begin{pmatrix}\varphi&0&1\end{pmatrix}
\\ & \quad+
\frac{3-\sqrt{5}}{8}
\frac{\varphi^2}{1+\varphi^2}
\begin{pmatrix}-\varphi^{-1}\\0\\1\end{pmatrix}\begin{pmatrix}-\varphi^{-1}&0&1\end{pmatrix}
\\ & \quad +
\frac14 \begin{pmatrix}0\\1\\0\end{pmatrix}\begin{pmatrix}0&1&0\end{pmatrix}
,\end{align}
where $\varphi$ is the golden ratio, which is pretty awkward, particularly when you can just notice that
\begin{align}
\rho
=
\frac14 \begin{pmatrix}1&0&0\\0&0&0\\0&0&0\end{pmatrix}
+\frac14 \begin{pmatrix}1&0&1\\0&0&0\\1&0&1\end{pmatrix}
+\frac14 \begin{pmatrix}0&0&0\\0&1&0\\0&0&0\end{pmatrix}
\end{align}
and take it from there. As I said, if you're being asked to provide an ensemble decomposition then all you need to do is provide one that works.
