I did manage to install the legacy driver under Windows 8.1 (with the help from a post on anandtech and a friend)! The way I did it:
Start the installation process of the driver, you may as well continue with it until the installation of the display driver fails if you want the other components as well. Remember where you unzipped the installation files to (Usually C:\AMD\ ...) and open the folder where the display driver is found (In my case C:\AMD\AMD_Catalyst_12.6_Legacy_Win8\Packages\Drivers\Display\W86A_INF). You will soon install one of the drivers there.
But before that, go to the Device Manager, find your graphics card (with the default Microsoft Driver), right click it, click uninstall driver. I did also check the box to uninstall the software but do not know if this is necessary. However, your display will go black for a second and only a rudimental screen resolution is restored but that's what we need for the moment.
Now go back to the open folder with the display driver, right click the C8*.inf (in my case C8146670, the 8 at the beginning however denotes Windows 8) and choose "Install". After allowing installation and getting a prompt that it was successful, head back to the Device Manager, search for altered hardware. Your graphics card will be found, the screen will again go black for a short while (personally, I enjoyed listening to the Windows sounds at that point) and afterwards the graphics card is installed with the AMD display driver!
I do not know who to blame (if there is someone to blame) for making it this difficult, but no need for a new graphics card or an older and slower system whatsoever!
TL;DR: Uninstall graphics card, install AMD driver manually using the appropriate .inf, reinstall the graphics card. Enjoy. In this order.
03:14 PM by