In this paper we present an accurate numerical scheme for extracting inter-atomic exchange parameters ($J_{ij}$) of strongly correlated systems, based on first-principles full-potential electronic structure theory. The electronic structure is modelled with the help of a full-potential linear muffin-tin orbital method. The effects of strong electron correlations are considered within the charge self-consistent density functional theory plus dynamical mean-field theory (DFT+DMFT). The exchange parameters are then extracted using the magnetic force theorem, hence all the calculations are performed within a single computational framework. The method allows to investigate how the $J_{ij}$-parameters are affected by dynamical electron correlations. In addition to describing the formalism and details of the implementation, we also present magnetic properties of a few commonly discussed systems, characterised by different degrees of electron localisation. In bcc Fe we found a minor renormalisation of the $J_{ij}$ interactions once the dynamical correlations are introduced. However, generally, if the magnetic coupling has several competing contributions from different orbitals, the redistribution of the spectral weight and changes in the exchange splitting of these states can lead to a dramatic modification of the total interaction parameter. In NiO we found that both static and dynamical mean-field results provide an adequate description of the exchange interactions, which is somewhat surprising given the fact that these two methods result in quite different electronic structures. By employing Hubbard-I approximation for the treatment of the $4f$ states in hcp Gd we reproduce the experimentally observed multiplet structure. The calculated exchange parameters result to be rather close to the ones obtained by treating the $4f$ electrons as non-interacting core states.