We show that the time-dependent single electron, nuclear density matrix of an interacting electronic system coupled to nuclear degrees of freedom can be exactly reproduced by that of an electronic system with arbitrarily specified electron-electron interactions coupled to the same nuclear degrees of freedom, given the initial density matrix of the interacting system. This formalism enables the construction of rigorous time-dependent density-functional theories to study nonadiabatic electronic dynamics. We obtain the Runge-Gross and van Leeuwen theorems as special cases in the adiabatic limit.