Payback hits harder when you act second, which is often enough in important battles, and the 20 BP makes a difference (with that 90 base attack).
Sturdy shouldn't even be taken into account when discussing Magnezone. Why would you sacrifice most of its HP when surely you have other options available. Magnezone without Sturdy should function exactly the same as Magnezone with Sturdy in-game.
Heracross's advantage over Scrafty is that it can outspeed and OHKO some of the fliers (namely the birds) that would destroy it if it happened to be slower.
Also, it's no problem to just catch the Marill with the right nature. It takes less time to do so than catching a Sigilyph with lots of Ultra Balls, and Sigilyph is in high tier. You can even evolve it with a Rare Candy if you're impatient, and it'll serve you well against Clay. Azumarill is even slower, though, and has a worse defensive typing. You'll need a lot of items to maintain it while it's dishing out those OHKOs left and right.
Also, I doubt Heracross will be any weaker than the rest of your team when you catch it before Elesa. It's definitely going to be stronger than all your Pokemon waiting for an evolution (which form the entirety of Top tier and most of High tier by the way) at that point, and it only keeps getting better as the game progresses. It loses only the desert area if compared to Scraggy, and you could always backtrack there to train Heracross and catch it first since the main road only takes a minute or so.