I figured out how to fix this - this worked for both my and my friend's iPhones.
1. Connect to iTunes in recovery mode, start recovery.
2. When you see the "Spinning wheel" on iPhone's screen - EJECT THE CABLE IMMEDIATELY.
Wait for 10 seconds
3. Reinsert the cable - the restoration process will begin.
Looks like Apple has a faulty algorithm that marks some iPhones as damaged even if they are not(or they simply want you to buy more new devices :)).