In mixed quantum-classical molecular dynamics few but important degrees of freedom of a molecular system are modeled quantum mechanically while the remaining degrees of freedom are treated within the classical approximation. Such models can be systematically derived as a first-order approximation to the partial Wigner transform of the quantum Liouville-von Neumann equation. The resulting adiabatic quantum-classical Liouville equation (QCLE) can be decomposed into three individual propagators by means of a Trotter splitting: (1) phase oscillations of the coherences resulting from the time evolution of the quantum-mechanical subsystem, (2) exchange of densities and coherences reflecting non adiabatic effects in quantum-classical dynamics, and (3) classical Liouvillian transport of densities and coherences along adiabatic potential energy surfaces or arithmetic means thereof. A novel stochastic implementation of the QCLE is proposed in the present work. In order to substantially improve the traditional algorithm based on surface hopping trajectories [J. C. Tully, J. Chem. Phys. 93, 1061 (1990)], we model the evolution of densities and coherences by a set of surface hopping Gaussian phase-space packets (GPPs) with variable width and with adjustable real or complex amplitudes, respectively. The dense sampling of phase space offers two main advantages over other numerical schemes to solve the QCLE. First, it allows us to perform a quantum-classical simulation employing a constant number of particles; i.e., the generation of new trajectories at each surface hop is avoided. Second, the effect of nonlocal operators on the exchange of densities and coherences can be treated beyond the momentum jump approximation. For the example of a single avoided crossing we demonstrate that convergence towards fully quantum-mechanical dynamics is much faster for surface hopping GPPs than for trajectory-based methods. For dual avoided crossings the Gaussian-based dynamics correctly reproduces the quantum-mechanical result even when trajectory-based methods not accounting for the transport of coherences fail qualitatively.