I'm generating a few thousand addresses to test a contract, could I do that in Solidity, or do I have to use something like ethereumjs-lib ?
To answer the specific question, Solidity cannot generate addresses. As far as I'm aware, no one has written such a library, because it could not be safely used on a public network, and on a private network one could use an ordinary program. (Using such a thing on a public network would allow anyone to read the private key--certainly undesired.)
What precisely are you doing with these addresses?
If you don't need to send from them, you can just randomly generate thousands of twenty-byte hexadecimal numbers. If you want to send from them on a test network, you can use the latest version of testrpc, which can fake sending from an address. If you need actual addresses, you'll probably need something like ethereumjs.