When approaching the continuum limit in lattice QCD or other theories in a setup with topological sectors, conventional update algorithms experience a particularly severe form of critical slowing down that is caused by high action barriers between the sectors. The qualitative scaling behavior of this critical slowing down appears to be universal across different update algorithms and (gauge) actions. We demonstrate that a combination of Metadynamics with parallel tempering, along with other modifications, can significantly reduce autocorrelation times while avoiding the need for reweighting. We also discuss strategies to extend the methods to QCD simulations with dynamical fermions, and present first results for $N_f = 2$ simulations at unphysical pion masses.