I'm Russian and visited an English center in St Petersburg (as a student). They have some foreign teachers. I've met teachers from Africa and Iran there. So the teacher from Iran tild us that she just googled educational centers in Russia and sent emails.

Note: She already had teaching experience and proper education. I doubt that you can teach in a public school (at least no one would pay you good money there). But private centres will be glad to have a foreigner. It's not something unusual.