Alternative origins for the lungs

Question

The terrestrial "vertebrates" of my planet must breathe air, and therefore must have lungs of some kind. They are descended from fish-like creatures, which breathe through gills.

However, I would like to - if possible - have an alternative origin for the animals' lungs. On Earth, lungs developed from the swim bladder of bony fish, which was an air-filled organ lined with blood vessels.

So, what organ:

• Could be beneficial to fish-like creatures
• Could evolve into a lung(s)
• Would not be a swim bladder

On the end result:

1. It must be capable of sustaining megafauna
2. It must lead to a single passage in the mouth and two nostrils (So no tracheae)
3. It should, preferably, not be a copy of any invertebrate lungs either (e.g. book lungs)

The ancestral organ mustn't be some really specialized adaptation, it has to be something that a lot of fish should have. Otherwise, it evolving into the respiratory system of a whole superclass of diverse land fauna just doesn't seem realistic.

What I mean by that is; take fish. Air bladders aren't a fringe phenomenon found in one species, neither are gill arches and suction feeding or living in anoxic waters. We don't have to resort to obscure evolutionary steps in order to explain something that is often used as proof of evolution being impossible. Similarly, my aliens' lungs should be developed from a wide-ranging organ.

Answer 1

The only alternative organ I can think of that has access to plenty of oxygen is the skin.

Obviously insects have evolved absorption of oxygen through their skin, but if your ecology is essentially evolving from fish-like animals already then perhaps an alternate evolutionary pathway is for some to evolve blood vessels passing through external layers close to the skin prior to being circulated throughout their body.

The oxygen absorbed through essentially external bronchioles. These could be located in external appendages (such as fins) or simply on the body. It is obvious that plenty of air needs to pass through these though, so the only situation I would expect is fast moving fish through the air, such as perhaps a possible derivative of a flying fish (shown below). Such a fish could then evolve more land-based limbs or air-based wings to venture over land which at that time could be evolutionarily vacant.

Of course over time it may be necessary to develop protection of your bronchioles, as they may be quite delicate. It is then easy to envisage folds in skin to support protected areas - much like gills are today in fish but for the air. Or external lungs, if they can fold in on themselves to 'pump air' through them but also to protect them.

Such a large, perhaps internalised, surface area can then support your megafauna.