A lot of this is obviously highly situation-specific. I'll mention a few points that I think are likely to apply to someone in your situation, but it's quite possible that there are reasons why this or that wouldn't apply in your case.
As a general note, finding a job far from where you are is difficult. Combining an international move with a career change will compound the difficulty. While a lot of companies will accept phone interviews, some will insist on an in-person interview, and the ones that don't are likely to select a candidate that they've seen personally all else being equal. Having some positive connection can often tip the balance towards you: “he comes with a recommendation from Prof. X, the last candidate who did was great” is a lot better than “he comes with a recommendation from Prof. X whom I've never heard of”.
Most companies have little long-term visibility. In France, most programming jobs have a 3 month latency (if I resign, I'm still supposed to work for the company for 3 months, and if I'm fired, the company still owes me 3 months (or more) of salary), so it's common to say “if you hire me I can come to work for you in 3 months plus 1 week”. Even 3 months is considered a long time: companies that are hiring usually want someone ASAP and ask if you could possibly come to work for them sooner. Anything beyond that would be unusual. Most companies have no idea who they'll want in 6 months.
I advise you to research teaching jobs in your desired locale. Even if you don't intend to stick in this job, plan to spend a year teaching as a bridge.
There are plenty of programmers on the market. Programmers, per se, are not in high demand. Good programmers or programmers with specific skills are in high demand. Your lack of programming experience is a definite minus, but the PhD in math can be a plus in the right place. Most employers will start with a certain stereotype of what a PhD in math with teaching experience would be: a quick study, autonomous, good at explaining things, but untested at teamwork and unlikely to have internalized the practical aspects of shipping code now rather than when it's working to perfection.
(Personal story time: I did a PhD in theoretical computer science, and then switched to a job in industry. I think I was hired for two reasons: my PhD advisor knew the person who recruited me (so his recommendation carried a lot of weight), and they basically told me “you know nothing about our business, but you have some background in the general domain, you can absorb new material quickly and write it up in terms that people can understand. We have a tech writer position.” After a few months I switched to a position that involved coding.)
With a PhD in math, you should look for domains where your math background will be useful, even if it's unrelated to the math you did in your PhD. Finance is a possibility; there are high-paying jobs there, and this is one of the few industries where you might start out applying your knowledge of differential equations and probability and learn coding on the job. A number of engineering jobs involve computer simulations based on mathematical models of physical phenomena. Arithmetic might lead you to cryptography, but that involves more specialist knowledge. The list of examples could go on: there are plenty of niches where a math PhD might fit in, and they tend to value their employees well because of the relatively rare skills they require; the flip side of the coin is that these are all small fields and there aren't openings every day.
