I'm on 737 classics but I'm sure the philosophy is similar....
Air and Electricity are required for start.
The APU might be running but unable to supply air for some reason. In that case one engine is started at the gate using the external air supply. With one engine running, there is an air supply to start the other, via the Cross-bleed procedure. Therefore there's no reason why the sircraft cannot push back and start the other engine afterward.
A crossbleed start involves using more air pressure than is available at idle rpm, so the running engine is revved up to an intermediate setting before the cross-bleed start is done. We need 30 psi of air pressure, which means setting about 35% N1 (as opposed to the idle rpm of about 21%). For this reason, it is not done while pushing back, only after brakes are set.
Pushing back with asymmetric thrust above idle could cause problems for the tug crew, especially if using a tow-bar, especially on slippery surfaces.
Or the other possibly is that the APU is running, but the generator is unserviceable. So the APU can supply the air for the start, but not the AC
power. So the first start is done at the gate using the ground power supply. Once the first engine is started, its generator supplies the electricity. The second start therefore is done with the APU air and the power from the running engine generator.
(On the 737 its possible to start using DC power, i.e. only the battery and any air supply, but its long and complicated so would never be done by choice. I had to do it once. It takes ages.)
Why your flight started both engines at the gate I don't know. Maybe they started one, and were held on stand for other traffic, so decided to start the other anyway. Or if they were dependent on ground supplied air or electricity, they possibly thought - "what the heck - might as well start both here". Then the cross-bleed start procedure (not particularly complicated or time-consuming) is unnecessary.
Regards - musang