In this paper we argue that the electron skew-scattering on paramagnetic impurities in non-magnetic systems, such as bulk semiconductors, possesses a remarkable fingerprint allowing to differentiate it directly from other microscopic mechanisms of the emergent Hall response. We demonstrate theoretically that the exchange interaction between the impurity magnetic moment and mobile electrons leads to the emergence of an electric Hall current persisting even at zero electron spin polarization. We describe two microscopic mechanisms behind this effect, namely the exchange interaction assisted skew-scattering and the conversion of the SHE induced transverse spin current to the charge one owing to the difference between the spin-up and spin-down conductivities. We propose an essentially all-electric scheme based on a spin-injection ferromagnetic-semiconductor device which allows one to reveal the effect of paramagnetic impurities on the Hall phenomena via the detection of the spin polarization independent terms in the Hall voltage.