Unfortunately, I can't do the standard solution. It seems steam gave me (and a bunch of other people) a 5x5x5x5x5 key, instead of the 4x4x4x4 usual taleworlds key. That happened in the last christmas sale.
So now, I can't use the talesworld setup. I tried that, but it asks me for the 4x4x4x4 serial key. There is a converter on the talesworlds forums, but it does not work at the moment, and if I use it I'll probably lose the characters.
So I have to wait until an official fix of this mess, or use the hacky way Garrus suggested (I hope it works, many thanks Garrus!)
Currently reinstallating warband from steam, I'll edit this.
Aaaand it works with the Garrus solution!