What foreign language is the most common in Serbia? In which language have I the most chances to communicate with locals (in shops, railway stations, hostels etc.) if I don't know Serbian?
Language: Serbian 90.1% (official), Hungarian 3.8%, Romany (Gypsy) 1.1%, other 4.1%, unknown 0.9% (2002 census)
So in that respect, Hungarian is the next best bet. However, that's 'official' languages and was a 2002 Census - if you keep on top of world affairs, things have changed a lot in that area since then.
So reading further down the same page:
So based on that - English is a pretty good bet, if you speak that (which it seems you do) - ask the young people questions for a better success rate. If you speak German or French, I'd be asking older people for directions etc.
Any language of the Serbo-Croatian family. This group includes besides Serbian, Croatian, Bosnian and Montenegrin. These languages are pretty close to each other. They only started to really move apart when Yugoslavia broke up.
It also depends on the place where you go. If you go to a colorful place like the Vojvodina, the choice becomes larger. This province has six official languages: Serbian, Hungarian, Slovak, Croatian, Romanian, and Ruthenian. In Central Serbia you will also find places where people speak Albanian or Bulgarian.
As in many other countries too, English is becoming more and more popular. This is especially true for a more younger population, but not only.
Apart from that, use the international master language, and communicate with hands and feet. Learn some basic phrases in Serbian. Knowledge of the Cyrillic alphabet could be useful too, it is still widespread in Serbia. The Serbian language uses both Cyrillic and Latin alphabets.
English is really widespread, so that would be your best bet. They might have trouble understanding, and you will probably have a lot of trouble understanding (since they have thickish accents). Unless of course you spoke another Yugo language, but I am assuming you don't since most people who do know that there is basically no difference.
As for whether Russian is common,it was in older generations but now English is more commonly taught as a second language.