Magnetic impurities at surfaces of superconductors can induce bound states referred to as Yu-Shiba-Rusinov (YSR) states within superconducting gaps. Understanding of YSR states with spin-orbit coupling (SOC) plays a pivotal role in studies of Majorana zero modes. Spin polarization of a zero-bias peak (ZBP) is used to determine its topological nature. Here we investigate the YSR states of single magnetic impurities at the surface of Pb using the fully relativistic first-principles simulations including band structure of Pb and five 3$d$ orbitals of the impurity in the superconducting state. We show that for single Fe and Co impurities, strong SOC can induce a ZBP with rotation of the impurity magnetic moment and that the ZBP has large spin polarization in contrast to effective model studies. Conditions for a ZBP from a single magnetic impurity are discussed. Our results are relevant to longer atomic chains considering their canting and noncollinear magnetism.