Honestly, this is why I don't complain very much about biometrics and databases, because the realistic alternative (potentially being detained at the border while they try to guess whether your passport is forged/altered/stolen) is much worse.
If you have thousands of dollars and a week or two to waste.
> Canada or Mexico
If you can get a visa for those places. Both of your ideas are things I, as an affluent Westerner, would try if the US government stuck me on a no-fly list, but for the people targeted they may simply not be possible.
Horribly inconvenient, but not a blanket ban.
I'm having trouble finding dates for some of these cases and none seem to have happened while GWB was POTUS. But here are a few links involving US citizens whose ability to travel into and out of the US were curtailed. None of the following links are the case I remember, which involved an American who was a father (from NY?) and who had been stranded from his family in the US.
• U.S. Veterans Stranded Overseas|Challenge No-Fly ‘Terror’ List [0]
• ACLU challenges constitutionality of no-fly list [1]
• No-fly list grounds another San Diegan [2]
• How a Young American Escaped the No-Fly List [3]
[0] http://courthousenews.com/u-s-veterans-stranded-overseaschal...[1] https://www.publicintegrity.org/2010/06/30/2631/aclu-challen...
[2] http://www.sandiegouniontribune.com/news/watchdog/sdut-no-fl...
[3] https://theintercept.com/2016/01/21/how-a-young-american-esc...
EDIT: formatting