Well, first you ask Microsoft support. That does not go well: they tell you to send them your Surface. But that's not really a good option - to lose your tablet for two weeks over a software problem? That's just not fair!
So, next, you try googling for help. But all you ever find are similar unanswered pleas for help, which usually end up being either unanswered or closed by moderators.
But fear not, as you CAN solve this, and you don't even need to do crazy things like making your own recovery image, or downloading one from weird Chinese sites.
HOW TO REINSTALL WINDOWS 8.1 ON YOUR SURFACE PRO WITHOUT A RECOVERY PARTITION/USB
Obtain a Windows 8.1 ISO. I can't tell you where to obtain one, but it is not a hard task.
The flavor Surface Pro uses is Windows 8.1 Pro x64. I used the EN-US version, as I have an American Surface, so I can't verify how other languages will work.
Burn that ISO to a USB drive. I suggest using Rufus for that: http://rufus.akeo.ie/
Boot your Surface from the USB drive.
To do that, hold the volume down button when turning on your Surface
Install Windows 8.1.
It will ask you for an install key, and might not accept your real Surface key. The reason for that is that the installer for Windows 8.1 does not accept Windows 8.0 keys (and your Surface might have one of those).
To proceed with installation, you will need this install key:
After installing the OS, you'll notice that it's not behaving quite right, for example, there are 4 rows of tiles on the start screen instead of three.
Go to Windows Update, and install everything.
If you installed with the install key, use this utility to get the original Windows key: http://forums.mydigitallife.info/thr...uct-Key-Viewer
Choose the "MSDM" option, copy that key, and activate Windows with it.
Enjoy your happily recovered Surface.
So there. That was a little guide on how to recover a Surface Pro without a recovery drive. I was in this situation myself recently, and Microsoft offered me to send my Surface to them - which would've cost me $200, as I live in a different country from the one my Surface came from, and also would've meant living without my tablet for a month or even longer. So I just fixed it all myself.