It is shown that the nonequilibrium self-energy of an interacting lattice-fermion model has a unique Lehmann representation. Based on the construction of a suitable noninteracting effective medium, we provide an explicit and numerically practicable scheme to construct the Lehmann representation for the self-energy, given the Lehmann representation of the single-particle nonequilibrium Green's function. This is of particular importance for an efficient numerical solution of Dyson's equation in the context of approximations where the self-energy is obtained from a reference system with a small Hilbert space. As compared to conventional techniques to solve Dyson's equation on the Keldysh contour, the effective-medium approach allows us to reach a maximum propagation time, which can be several orders of magnitude longer. This is demonstrated explicitly by choosing the nonequilibrium cluster-perturbation theory as a simple approach to study the long-time dynamics of an inhomogeneous initial state after a quantum quench in the Hubbard model on a 10×10 square lattice. We demonstrate that the violation of conservation laws is moderate for weak Hubbard interaction and that the cluster approach is able to describe prethermalization physics.