How to find a high quality PhD advisor in another country? I an currently finishing my first year in a Masters program in Computer Science / Mathematics and thinking about getting a Ph.D. I'm not really sure, however, that I want to make my Ph.D. with the same thesis with which I'm getting my Masters degree. 

I heard the opinion about Ph.D. as "doing interesting (for you) stuff, development your skills and even getting paid for it". But it seems too unrealistic for me, especially in my city/country (Russia). Probably I can think about getting a Ph.D. in another country, but how can I manage to do it without a proper Ph.D. advisor? Probably, I can determine an area of my interests, but how can I determine if it is suitable for a Ph.D. or not? And how can I find the person who can guide/help me with it?

I'm feeling a little bit nervous when thinking about writing to a complete stranger in another country "I want to do PhD under your supervision" or something like this.
It depends on your credentials and references. But having good record enables you to apply to many good schools (e.g., Princeton, MIT etc.) in the US/Europe, via dedicated online application sites. So you do not need to personally contact anyone. 

The other option is to use Findaphd.com, and other dedicated mailing lists who solicit PhD applications.

Of course, sending emails to professors, without knowing in advance whether they have the money to support a PhD student, is possible but has quite a low chance of success.  

You might also use your existing professional connections within your local academia to seek potential PhD opportunities.