So here's my suggestion: create a new Marine Corps MOS (Military Occupation Specialty, i.e. job) of Air Marshall or Flight Security or whatever. One would have to pass a security background check and would be heavily trained in close-quarters hand-to-hand combat. They would be armed. They would also have to be inconspicuous, meaning they would have to be allowed to grow their hair and facial hair. By making this an MOS there would be a fairly large number of Marines, a few thousand, whose job would just be to fly around and protect the planes from terrorists. Put one or two on planes originating or landing in the United States.
Why think this will work? Because it did before. In the aftermath of World War I, gangsters were robbing the US mail system. It became such a chronic problem that they decided to put a couple of Marines on the trains carrying registered mail. And the robberies stopped. The linked article gives some excerpts from the training manual given to the Marines charged with the security of the mail:
Q. Suppose he [the robber] is using a gun or making threats with a gun in trying to escape?
A. Shoot him.
Q. Is there a general plan for meeting a robbery?
A. Yes; start shooting and meet developments as they arise thereafter.
Q. If I hear the command "Hands Up," am I justified in obeying this order?
A. No; fall to the ground and start shooting.
Q. Is it possible to make a successful mail robbery?
A. Only over a dead Marine.
Now I know there are people who would not feel comfortable on a plane with someone who had weapons and had been given orders like this. That would be the terrorists. Like it or not, the Marines have a reputation of being a force to be reckoned with. As was the case with the mail system, 99% of the battle would already be won just by having the Marines there as a deterrent. The other 1% would be over in a few seconds.