you haven't posted a link or anything for the motors your using, so I'm just assuming your using the yellow ones with the black tires.
4x1.2v will give you 4.8v total, it will be less than that once you run them through your shield but you still should be good. The good thing about the single AA batteries is if you did find that the volts dropped too much (around your minimum 3.5v) you can add another battery and switch to a 5AA holder(or less for other bots and stuff) without having to worry about a whole new battery pack for each different build.
I have 5 fully charged AA's(6 volts) hooked up to my adafruit shield and my multimeter is telling me that the batteries are 6.5 volts and the output of the shield where the motors are connected reads 4.92 volts (two motors at full speed running in the air), so it dropped around 1.5 volts, that's with fresh batteries so the output reading may change after running it for a short while. You'll need to try your own experiments.
The "23000mAh or greater" will determine how long you can run the motors before they drain to a point where you need to recharge them again, if you are running four motors the batteries will drain faster than a robot that uses two so look for batteries with high mAH, for the most part if your just turning on your bot for short periods of time you should shouldn't really have worry too much about them dying anyways. You can always have two sets, one charges while you use the other if you needed to. I mentioned the Energizer 23000mAh because that's what I use and they do the trick there may be something better?
ps: the mAh label is really small and on the top and side of the battery, not too sure if it's advertised on the package or not? so stay sharp