If Bizantines are screwed Russia is going to convert to Catholicism sooner or later. Islam is out of question due to dietary laws-ban of pork and alcohol is not good idea in Eastern European forest zone.
I know the thread isn't exactly about this, but tbh I think the pork and alcohol ban is less of an issue than you might think.
Untill they abandoned being step nomads (to the larger extent) the Turks got away with all sorts of stuff. Some were practically polytheists, many consumed alcohol and whatever meat they could get their hands on (pork included). Even late into their history, the practices of some Turks was so far removed that the Russians had to abandon categorising people by religion and instead did so by language. Taken far enough, technically speaking the nomadic lifestyle is completely haram as the Quran also mentions hunting (a mainstaple of nomadic life) as forbidden.
In short, whilst less likely than Christianity due to political reasons, I think the old idea that Pork and Alcohol itself would be a barrier isn't the case. Hell, when speaking to muslims in the past about this, the concencus I got was that it might be considered ok to look at the pork as neccesary to survive (something perfectly acceptable to Islam), the alcohol would be permissable under medical means (keeping warm).
Directly to the topic at hand, I think Nestorian Russia isn't impossible.