First, flying on credit isn't nearly as easy as you make it out to be. Yes, a bunch of companies are buy now, pay later. They fall into two groups. The first does it based on your credit. The second is a layaway plan - by the time you get on the plane you've managed to pay in full. Ex-cons struggling to get a job usually have neither. Nobody wants to give money to a person who looks like they are trying to disappear. (Because you just know your money is going to disappear with them...)
Second, a lot of your plans require going to countries where you need another language. That's going to be a challenge for most ex-cons.
Third, while the French Foreign Legion is romantic and all, they won't take you if they find you have a criminal record. Other foreign legions are similar. They might not find out, but do you want to spend your life savings betting on that?
Fourth, marrying someone from another country is an uphill battle for someone who lacks a job. Particularly when most of the women from those countries looking to marry an American would like to wind up in the USA rather than the reverse.
These are all amazing plans, and I'm sure that some succeed with each. But they're going to work out poorly for most ex-cons who try them.