I understand that teaching positions are mostly reserved for Full time Phd Holders and is getting increasingly tough. So how difficult it will be, post MS, for an international applicant to secure a full time instructor job.
In the US, community colleges (i.e., two-year colleges) sometimes hire faculty with master's degrees. At four-year colleges and universities, it's basically impossible to get a regular faculty position without a Ph.D. (It might theoretically be possible, but only under extraordinary circumstances, for example a pioneering industrial researcher who never completed a Ph.D.)
So that means you would have to target community colleges. How difficult that would be depends on the circumstances, and it's important not to assume it's easy to get such a job just because the institution is less prestigious. I don't think you'll be able to get a full-time instructor position without some prior teaching experience, since you'll need to demonstrate your teaching abilities.
Being an international applicant shouldn't be a big deal overall (assuming you have authorization to work in the U.S.; see Paul Garrett's comment below), but it may come up in several ways, such as English proficiency. The most annoying may be that teaching experience is other countries is sometimes not taken as seriously. It can be difficult for evaluate for people unfamiliar with the system it took place in, and it may involve students who are very different from typical U.S. college students.
I have seen certain Master students get a faculty position in the uni itself where they completed the course.
I've never seen that happen for a regular faculty position in the U.S. Occasionally, a master's student may be kept around for a while as an adjunct to teach low-level courses nobody else wants to teach, but this is generally not a well-paid or respected position. Someone with truly exceptional teaching skills might be retained long-term in a position with a title like "senior lecturer with security of employment" (not a regular faculty member but reasonably paid and without fear of abruptly being fired), but there are not many such positions and they are not easy to get.
What other degrees/certificates can help tip the scales in my favour?
I don't think any other degree or certificate will play an important role. If you find an opening for which the hiring committee genuinely doesn't care about having a Ph.D., then teaching effectiveness will be the primary criterion. Any evidence of excellent teaching will be helpful, but other degrees or certificates are not generally a compelling form of evidence.
