Critter Question

Would it be possible to grab a normal creature from one of the established PvE factions (say..Tuatha de Dannon) and give it Fly as a travel power?

No, you cannot edit the powers of standard critters.