The first question is what are the relays being used to turn on? Because maybe a transistor could do the job for you instead? You are going to need transistors anyway to drive the relay. Check this pic for the type of configuration
Note the protection diode. The input will be the Arduino pin, you can try a 1K resistor.
The Arduino only has 14 digital outputs so you would need to do some multiplexing to get this to work.
There are many options you could use like shift registers or decoders or even something like Charlieplexing, which you can find lots of info on these.
For starters check out this application note from ST www.st.com/stonline/books/pdf/docs/13709.pdf
There are even IC's that can do this for you. Just be careful with relays and make sure that you put in the protection diode otherwise some of your silicon can go up in smoke. Also remember a relay suffers from contact bounce and can be noisy not just from a sound point of view but also electrically. 300 relays clicking away might make a bit of noise and be a bit expensive as well.
I found this in the Playground now as well: http://www.arduino.cc/playground/Main/InterfacingWithHardware#Multiplexing