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 Alfven velocity. Our method is applicable on scales much larger than the ion inertial length, bypassing the microscopic scales that must be resolved in conventional PIC methods, while retaining the full kinetic nature of the CRs. We have implemented and tested this method in the Athena MHD code, where the overall scheme is second-order accurate and fully conservative. As a first application, we describe a numerical experiment to study particle acceleration in non-relativistic shocks. Using a simplified prescription for ion injection, we reproduce the shock structure and the CR energy spectra obtained with more self-consistent hybrid-PIC simulations, but at substantially reduced computational cost. We also show that the CR-induced Hall effect reduces the growth rate of the Bell instability and affects the gas dynamics in the vicinity of the shock front. As a step forward, we are able to capture the transition of particle acceleration from non relativistic to relativistic regimes, with momentum spectrum $f(p)sim p^{-4}$ connecting smoothly through the transition, as expected from the theory of Fermi acceleration.