Fewest-switches surface hopping (FSSH) is perhaps the most widely used mixed quantum-classical approach for the modeling of non-adiabatic processes, but its original formulation is restricted to (adiabatic) population terms of the quantum density matrix, leaving its implementations with an inconsistency in the treatment of populations and coherences. In this article, we propose a generalization of FSSH that treats both coherence and population terms on equal footing and which formally reduces to the conventional FSSH algorithm for the case of populations. This approach, coherent fewest-switches surface hopping (C-FSSH), employs a decoupling of population relaxation and pure dephasing and involves two replicas of the classical trajectories interacting with two active surfaces. Through extensive benchmark calculations of a spin-boson model involving a Debye spectral density, we demonstrate the potential of C-FSSH to deliver highly accurate results for a large region of parameter space. Its uniform description of populations and coherences is found to resolve incorrect behavior observed for conventional FSSH in various cases, in particular at low temperature, while the parameter space regions where it breaks down are shown to be quite limited. Its computational expenses are virtually identical to conventional FSSH.