The reason this is happening is because in some instances of Windows 8.1 Safe Mode does not work correctly and only shows a black screen. What is actually happening is that your computer is in fact booting into "Safe Mode", but for some reason it doesn't load properly and instead of your usual Safe Mode desktop all you see is a black screen, sometimes with a mouse pointer and the words "Safe Mode" flashing in each corner of the screen.
This issue is not caused by problems with one's video card and/or drivers, as is erroneously suggested around the web.
The problem with Safe Mode is beyond this question's reach, perhaps being better addressed to Microsoft.
However the normal booting can be easily restored.
In order to return to the normal Windows boot you need to run this command at a Command Prompt (you may access one from the "Advanced Boot Options" menu) and restart the computer.
bcdedit /deletevalue safeboot
That should fix your problems.
Why does this happen and why none of the other methods work?
When you enable any sort of "Safe Boot" in msconfig a file called "safeboot" is added to the boot sector of your hard drive. When your system loads it first looks at the boot sector in order to decide what to do next, when it sees this file it boots into Safe Mode.
Normally this file is deleted after you exit Safe Mode, but since in this specific predicament you are unable to do so you are stuck in an endless loop.
System Restore will not work, because it only alters files on your hard drive and the registry. In other words - it does not touch the boot sector, which you need.
Repairing the Master Boot Record or the entire boot sector will not help, either, because there is nothing wrong with them. Repairing them usually means just replacing the boot files, so that if they are corrupted or damaged they will work again, but what you need is to delete a file.
However boot "manager" programs could help you, if they are configured with more advanced options.
Boot order screen and advanced boot options
None of the options in the boot order screen or advanced boot options remove the "safeboot" file. Choosing "Normal Boot" simply allows the booting to continue, while choosing any of the "Safe Mode" options loads up Safe Mode.