Is it allowed, considered safe, and done, to start the engines while the aircraft is moving under the push-back power? On one hand it seems like a big time saving, on the other hand the running engines are rather dangerous and there is still a wing-walker often present during the push back.
It is common. In fact, for aircraft parked at a gate (i.e. not a hardstand), it is quite uncommon NOT to start the first engine during pushback. The wing-walkers stay well away from the intakes, and with the engines at idle power, the danger zone isn't all that large - not nearly as large as if the motor were running at a high power setting.