The recently open-sourced V-REP simulator (http://www.coppeliarobotics.com) may suite your needs. I found it more approachable than Gazebo, and it can run on Windows, OSX, and Linux. Their tutorials are fairly straight forward. It has a ton of different ways to interface with it programmatically (including with ROS). It looks like there is even a tutorial for making a hexapod (http://www.coppeliarobotics.com/helpFiles/en/hexapodTutorial.htm), which you could probably use as a starting point if they don't already have a quadruped example available. Unforuntely, I believe the simulator is tied directly with the UI rendering, which I believe is not necessarily the case with Gazebo.
So, your program would have to use one of the many ways to interface with V-REP, and then feed the performance of a particular gait into some machine learning algorithm.
On the other hand, you could make your own simulator using an existing physics engine, rendering it with a graphics library. Bullet and OGRE, respectively, could be used for this purpose, if you like C++. There are tons of others for other programming languages.
I would also look into how researchers who work on gait generation do their simulations. There mighy be an existing open source project dedicated to it.