I am trying to restore my backup but it is asking to turn off "Find my iPhone" on the old device, which was stolen. How can I restore my backup?
Well I guess this might help you : iCloud: Remove your device from Find My iPhone
Remove an iOS device you no longer have
If you no longer have the iOS device because you gave it away or sold it, you need to remotely erase it before you can remove it.
Sign in to icloud.com/#find with your Apple ID (the one you use with iCloud). If you’re using another iCloud app, click the app’s name at the top of the iCloud.com window, then click Find My iPhone.
Click All Devices, then select the device.
Click Erase device, then enter your Apple ID password. Because the device isn’t lost, don’t enter a phone number or message.
If the device is offline, the remote erase begins the next time it’s online. You’ll receive an email when the device is erased.
When the device is erased, click Remove from Account.
All your content is erased and someone else can now activate the device.