Some possibly relevant information:
Grant and Vickers, "Block diagonalisation of four-dimensional metrics,"
http://arxiv.org/abs/0809.3327
De Turck and Yang, "Existence of elastic deformations with prescribed principal strains and triply orthogonal systems," http://zmath.sub.uni-goettingen.de/ZMATH/serials/en/search/zmath/?an=0544.53012
Tod, "On choosing coordinates to diagonalize the metric,"
http://iopscience.iop.org/0264-9381/9/7/005
In 3 dimensions, diagonalization is always locally possible, but in 4 it isn't in general (Grant and Vickers). This seems to be plausible based on counting degrees of freedom as in PAllen's #4, but it seems that a rigorous proof was nontrivial? I assume that "locally" means diagonalizing it exactly in some finite region, with the only obstruction to extending it globally being some kind of topological issue. (Globally, we don't even necessarily expect to be able to cover the whole manifold with one chart.) I assume they *don't* mean "locally" in the more trivial sense, which follows from the equivalence principle.
As others seem to have stated, I think staticity suffices (locally) in 3+1 dimensions. (I guess this is because staticity allows us to write the spacetime as a direct product of a time dimension with a 3-space, and diagonalization is possible a 3 dimensions.) More generally, the abstract of Tod says, "It is shown that diagonalizability of the metric generically imposes restrictions on the third derivative of the Weyl tensor when n=4[...]" (I don't have access to the whole paper.)
Because of the topological issues, I doubt that any amount of symmetry suffices to guarantee a metric that's diagonalizable globally. For example, take the direct product of a 3-sphere with a line of time. It has a very high degree of symmetry, but I don't think we can find coordinates that diagonalize the metric globally, simply because we can't cover the whole thing with one chart.