Most known four-dimensional cohomogeneity-one Einstein metrics are diagonal in the basis defined by the left-invariant one-forms, though some essentially non-diagonal ones are known. We consider the problem of explicitly seeking non-diagonal Einstein metrics, and we find solutions which in some cases exhaust the possibilities. In particular we construct new examples of neutral signature non--diagonal Bianchi type VIII Einstein metrics with self--dual Weyl tensor.