In Russia, almost every document about a person includes a patronymic, so everyone needs it. If your father has foreign name, you still have a patronymic. If your father is unknown, your mother gives you some patronymic soon after your birth. If she doesn't know the father's name, she may give you her own patronymic. If a baby is found, and nobody knows who is his father or mother, they give him some random patronymic.
For example, Harry Kasparov (Гарри Каспаров) has English/American name Гарри. It is not a Russian name. Each of his sons is Гарриевич, and each of his daughters is Гарриевна.
Besides, there are many Russians who are ethnic Georgians, Armenians etc, and their fathers had non-Russian names. All these Russians have patronymics. For example, Абе́л Ге́зевич Аганбегя́н (Abel Aganbegyan), who is ethnic Armenian.
As per comments by Danila Smirnov and Tzakrevskiy, if a child with rights to Russian citizenship is born in a country that does not use patronymics, he/she does not receive a patronymic when applying for the Russian citizenship. However, Danila Smirnov writes:
I just happen to know someone who was born in another country and did not have a patronymic in his birth certificate when he was registered for Russian citizenship. When he got his passport at 14 years, he had a dash in his "patronymic" field. On the other hand, it did cause some problems, so he had to legally change his name to get one.