I wouldn't say they had to be life-sized...I've seen
flying effects for Peter Pan,
Wizard of Oz, Aladdin, and others that have used "marionettes" for this
effect, or have "kabuki" style performers operating regular size puppets and the
backdrop is still the starry night sky, but the set of London's rooftops is all only a few feet tall AND covered in a layer of
Fog...As they leave "London", the set is dropped beneath the
stage or pulled off and the scene change for Neverland occurs then, slowly making a new
wagon of scenery come on (of strange plants/trees or Jungle like) depending on the production. You could also use regular sized dolls and add rods and dress them up accordingly. If you wanted to go life-size with the characters, you may as well do that kabuki style and just bring on 4+ technicians to
hoist up the kid actors and fly them (I've seen this done to great and not-so- great effects.) If you have fly space and authorization and money to fly the characters, FLY them w/ FX or whomever....Another idea....In every city, there is generally a puppet company. Work in tandem with them. Offer them tickets or free program ad. You may have to dish out some serious money for them to make you puppets for it. Now, since you wanted to get creative and use puppets, you could also do black-lighting, have "doubles" of the actors in "black-light fabric" costumes w/ masks or
blacklight makeup and have them "fly around"