We study heat kernels of Schrödinger operators whose kinetic terms are non-local operators built for sufficiently regular symmetric Lévy measures with radial decreasing profiles and potentials belong to Kato class. Our setting is fairly general and novel -- it allows us to treat both heavy- and light-tailed Lévy measures in a joint framework. We establish a certain relative-Kato bound for the corresponding semigroups and potentials. This enables us to apply a general perturbation technique to construct the heat kernels and give sharp estimates of them. Assuming that the Lévy measure and the potential satisfy a little stronger conditions, we additionally obtain the regularity of the heat kernels. Finally, we discuss the applications to the smoothing properties of the corresponding semigroups. Our results cover many important examples of non-local operators, including fractional and quasi-relativistic Schrödinger operators.