If two Air don't power the same drive and you've tried several cables, you might need to talk to the drive manufacturer. MacBook Air can power a SuperDrive that triggers a high power mode on the USB ports, and I have seen reports that they can push well over 950 mA to burn a DVD.
Basically, it's unlikely two MAcBook are are both under-powering one hard drive and more likely the drive only asks for 500 mA and that's not enough to power the drive's controller or perhaps that drive/controller is simply out of spec.
You can refer to Apple's KB article that covers USB 3 devices getting 900 mA at 5V as a feature of the MacBook Air, so that should be plenty of power for a drive to operate.
You might need to seek service for either the Air or the drive if you can't fix things with trying other cables. The operation with other devices is nice, but in the end, if you need it to work with the Air, you'll need to work through that by repair/replacement of something.
Using the System Information tool on OS X, you should be able to determine if the USB chipset is sending any data over to the Air - whether or not it is getting enough power or even getting to the point where it can signal how much power it would like as part of the USB enumeration process.