Relativistic collisionless shocks are associated with efficient particle acceleration when propagating into weakly magnetized homogeneous media; as the magnetization increases, particle acceleration becomes suppressed. We demonstrate that this changes when the upstream carries kinetic-scale inhomogeneities, as is often the case in astrophysical environments. We use fully kinetic simulations to study relativistic perpendicular shocks in magnetized pair plasmas interacting with upstream density perturbations. For amplitudes of δρ/ρ ≳ 0.5, the upstream fluctuations are found to corrugate the shock front and generate large-scale turbulent shear motions in the downstream, which in turn are capable of accelerating particles. This can revive relativistic magnetized shocks as viable energization sites in astrophysical systems, such as jets and accretion disks. The generation of large-scale magnetic structures also has important implications for polarization signals from blazars.