I have no experience of teaching in Central or Eastern Europe, but here are my impressions.
Being a native English speaker will often be a
preference, but that is all.
You say CELTA cert, but usually employers ask for "or
equivalent". An ITTT cert might be considered an equivalent by some employees, but no
online (only) course could be considered an equivalent.
On the whole, and based on your apparent fluency in English, and your American degree and experience, I would say it should not be impossible for you to find work. It's worth a try, both by responding to ads and putting your resume/CV online. You might want to emphasise your aptitude in business English.
Good luck
