We formulate a magnetohydrodynamic-particle-in-cell (MHD-PIC) method for describing the interaction between collisionless cosmic ray (CR) particles and a thermal plasma. The thermal plasma is treated as a fluid, obeying equations of ideal MHD, while CRs are treated as relativistic Lagrangian particles subject to the Lorentz force. Backreaction from CRs to the gas is included in the form of momentum and energy feedback. In addition, we include the electromagnetic feedback due to CR-induced Hall effect that becomes important when the electron-ion drift velocity of the background plasma induced by CRs approaches the Alfvén velocity. Our method is applicable on scales much larger than the ion inertial length, bypassing the microscopic scales th...