I just beat Brock within the restrictions. Took a video, but I can't post attachments yet. It was about 22-24 turns.
The Team
...
Hard the Wartortle Lvl 16 MVP, of course.
-Tackle
-Withdraw
-Water Gun
-Tail Whip
Very Hard the Caterpie Lvl 6. LVP.
-Tackle
-String Shot