I... honestly think I might be stuck.
I can't figure out any way to beat Samson, especially since I can't head back to Agate (so no Bull training, breeding, catching earlier pokemon, etc.) and I've already done the Crustle puzzle so I can't train against them either, so my only options for grinding levels are the woefully underleveled/unevolved (L. 51 Rufflet's the highest I've seen) pokemon in the Route 2 area/Celestine Cascade area.
Currently running...
Torterra (L. 64) with Wood Hammer/Earthquake/Crunch/Curse
Machamp (L. 63) with Dynamic Punch/Cross Chop/Rock Smash/Strength
Emolga (L. 64) with Acrobatics/Discharge/Cut/Light Screen
Grumpig (L. 64) with Psychic/Power Gem/Shadow Ball/Trick Room
Bouffalant (L. 64) with Thrash/Swords Dance/Megahorn/Reversal
and Gastrodon (L. 64) with Mud Bomb/Sludge Wave/Muddy Water/Recover.
I've managed to get as far as 1-1 with Grumpig v. Hawlucha, but I can't seem to beat Fly. Apart from hoping I get lucky with Bounce Grumpig (could teach over trick room/shadow ball and switch back afterwards), I'm thinking my only option seems to be training a wild Meditite or boxed Noibat (this will take a long time since I don't have any good grinding spots and the highest-leveled noibat I have is level 37).
EDIT: Seems I was a bit hasty about the wild levels being too low, about 5 minutes into playing afterwards I found a level 59 Noctowl
EDIT (Again): Seems Bounce did the trick. I can actually progress now, yay