Interactions between electrons and phonons play a crucial role in quantum materials. Yet, there is no universal method that would simultaneously accurately account for strong electron-phonon interactions and electronic correlations. By hybridizing the merit of the variational quantum eigensolver (VQE) and the variational non-Gaussian solver (NGS), we develop a quantum algorithm suitable for this type of correlated systems. This method tackles arbitrarily strong electron-phonon coupling strengths without increasing qubits and quantum gates, compared to purely electronic models. The benchmark on the Hubbard-Holstein model reveals the competition between charge density and spin density wave phases, quantitatively consistent with exact diagonalization.