Remember that they call their timeline removal "pruning." The thing about pruned branches is that they grow back if left alone. So now that pruning is no longer happening, the specific variation AoS got shunted off to may have happened.
He's not alone though. Even without any Stones he has his fanatical Children - and Ebony Maw at least seems to be on par with if not superior to Stephen Strange, who magically manhandled Loki with ease. And he's just one of them - Cull, Proxima, Corvus etc are as strong as Asgardians if not stronger. This also helps to explain why he was confident enough to hand stones around to other villains, he knew he'd have no trouble getting them back. Hela would be pretty outmatched I'd say.