Mikkel:
You may want to consider the use of an I²C I/O port device. Several of these placed at convenient places on your board could give you all the relay controls you need. Here is a link to a typical device.

http://www.semiconductors.philips.com/pip/PCA95...A9554.html

I would discourage you from the 4->16 line decoders. They are big packages that take a lot of space and really do not offer much over just a couple of serial to 8-bit devices. The hardwired "one-at-time" design that results from using the decoder also limits future flexibility wherein someone will come along and ask for multiple relays to be active at one time or to have active relays overlap or something.

Michael Karas