In the context of the development of NMR Fermi contact shift calculations for assisting structural characterization of battery materials, we propose an accurate, efficient, and robust approach based on the use of an all electron method. The full-potential linearized augmented plane wave method, as implemented in the WIEN2k code, is coupled with the use of hybrid functionals for the evaluation of hyperfine field quantities. The WIEN2k code is able to fully relax relativistic core states and uses an autoadaptive basis set that is highly accurate for the determination of the hyperfine field. Furthermore, the way hybrid functional approaches are implemented offers the possibility to use them at no additional computational cost. In this paper, NMR Fermi contact shifts for lithium are studied in different classes of paramagnetic materials that present an interest in the field of Li-ion batteries: olivine LiMPO4 (M = Mn, Fe, Co, Ni), anti-NASICON type Li3M2(PO4)3 (M = Fe, V), and antifluorite-type Li6CoO4. Making use of the possibility to apply partial hybrid functionals either only on the magnetic atom or also on the anionic species, we evidence the role played by oxygen atoms on polarisation mechanisms. Our method is quite general for an application on various types of materials. ; Comment: 39 pages