You can involve all the antitrust you want, as long as you don't lower the barrier to entry you're just lying to yourself and adding more useless middlemen.
Even if all of that were easy, you still want anti-trust regulation, because airlines are a cutthroat business. If you start up NerdBird Inc, specializing in SF-Austin flights, it is absolutely in the interests of United and American to undercut you on that route for as long as it takes to drive you out of business. Which will probably not be very long, as airlines are expensive to run and margins are thin.
World history clearly shows that lack of regulation inexorably leads to trusts, cartels, price fixing, price dumping, and all sorts of other anti-competitive agreements. It's trivially easy for a monopoly or cartel to raise their own barriers to entry to maintain their hegemony.
In fact, there's a good argument that the governmental barriers to entry you are lamenting were in fact driven by entrenched businesses as an example of regulatory capture and not a flaw in regulation itself.
If you let businesses get so big that not only are they not regulated, but they have taken over control of regulation itself, you're in a real pickle.
This is sort of like asking, "What is the minimum weight you can put on a seesaw before it tips?" The answer depends entirely what's on the other side.
One way to look at free markets is that they provide economic stability in the same way that tensegrity [0] structures provide physical stability. They work not because any element provides stability, but because — when very carefully composed together! — the elements exert opposing forces which all balance out leading to a stable system.
The "brilliant idea" of markets is taking advantages of forces that already exist — human selfishness and the desire to profit — and harness that to produce a system with some level of efficiency. The downside is that there's no real way to evaluate market participants in isolation.
I don't have experience in Hipmunk's field, but I do have experience, in another life, with CLECs, "competitive local exchange carriers." CLECs bloomed thanks to deregulation of their industry in the early 1990s, which is great -- but they were virtually all gone within a decade, not due to re-regulation but to the simple fact that achieving scale and profitability was monumentally expensive and difficult. The company I was at, Intermedia Communications, was bringing in close to a billion dollars of revenue annually by the time they threw in the towel and agreed to be purchased... and they still hadn't come close to turning a profit. But by that point the writing was already on the wall, and the industry was collapsing from hundreds of players to dozens. (The rise of wireless, of course, was the final death blow, but the industry was basically undead by then.)
I don't take Hipmunk's demise as a sign of "too much regulation" at all; airlines went through a similar contraction to CLECs, and what killed Hipmunk -- airlines choking off their pricing data -- will act to prevent any new competitors. That's not a function of too much regulation -- it's a function of not regulating the right things. What if airline pricing data was subject to FRAND ("fair, reasonable, and non-discriminatory") licensing?
Regulation is absolutely used too often to protect incumbents, but you simply can't blame lack of competition in every industry on too much regulation. Arguably, when implemented correctly, regulation can increase competition, not harm it.
I don't believe it's possible. You can't fight bad actors by hoping they'll just somehow lose. The unregulated "more competition" market quickly turns into a "less competition" market as the most ruthless parties establish dominance through whatever means necessary. Your barriers to entry, in the extreme case, become things like physical intimidation.
Remember that golden era when XMPP was federated across Facebook, Google Talk, AOL, etc. It wasn't perfect but did give users more options.