It turned out to be not so very hard to reprogram the Yubikey after all:
Code:
ykpersonalize -1 -ofixed=h:ff{put in some random 10 HEX-digits here} -ouid={put in some random 12 HEX-digits here} -v
In the code above, remove every { and }.
-1 - Change the first configuration. Change this to '2' if you want to change configuration #2 instead.
-ofixed - Public ID. If the key is in HEX-format (not modhex), the key should start with 'h:ff'. Else, if in modhex-format, it should start with 'vv'.
-ouid - Private ID/UID.
This is just a summary of what is needed to make it work. When running this, you are asked to type in a passphrase that will be used to generate the AES-key. After this is done, make a copy of your AES-key and upload it to Yubico.