I would second the Steyer AUG recommendation. The mag release is on the centerline of the gun, just behind the mag. The fire control is the trigger: it's two stage, the first stage being a single shot, the second stage being full auto. I'm right handed, but shoot what ever hand the situation requires. The AUG presents no additional challenges in this respect. They come up in the classifieds every so often, with enough price variation that you may be able to find one within your budget.
As to other guns, the best thing to do may be to physically try out various models. This needn't be done in the field... a simple handling test, to see if you can figure out a way to work fire select/mag release/safety off-handed would be all that's required. For instance, I know that I can manipulate the safety on a P-08 with my left hand, but it requires a bit of concentration. I could also shoot a standard bolt action left handed, but letting go of the front of the rifle in order to work the bolt is clunky.
It would be nice to see a Winchester Model 94 in airsoft...