It sounds like you have good skills and qualifications to start a career in TEFL. I would say you have a good chance of being accepted on a course. The CELTA and the Trinity Certificate are both highly recommended. You should try to get on a course with observed teaching practice. You can look throught the TEFL Training Discussion forum; there are many posts on this topic there. viewforum.php?f=11
As for visas, I can't say. That is something you would have to check with the consulate of the country concerned. I don't think that being made redundant from a job is a great hinderance, especially in today's job market, provided it is not for a serious matter.
All the best