Using the air to fly is the same as using the roads. By your argument, there is no "right to walk" or "right to drive" or "right to take a bus", therefore it would be OK to be made a prisoner by virtue of not being allowed onto public land.
It should be the government and not the individual whose freedom of movement is limited.
I don't agree with scanning but I also don't see you winning over many rational people with your comparisons. We need to come up with a better argument against the scanning that isn't so weak and easily shot down.
But let me try:
1. The machines are expensive and made by a company with a large lobbyist-budget.
2. The threat is over stated, these machines are overkill.
3. The machines grant marginal-at-best security beyond traditional methods.
4. The slow but steady psychological appeasement to being under closer and closer government scrutiny is a threat to democracy.
5. The airlines and their terminals are not private enterprises, while the security and regulations are pure government entities. Since TSA agents are government officials they ought to be bound by the constitution which protects against unreasonable search. If Macy's was forcing people to get cavity searches to enter their store, I wouldn't have a problem with it, I just wouldn't shop there. Being searched at an airport is a completely different situation than entering into a contract with a private party.
5a. The risk factor being so blown out of proportion makes a virtual-strip search of an average no-record citizen unreasonable.