per-particle is another story, that will be possible in 1.1
I think i remember Ondra saying per-element randomization would be quite complicated. I am not sure of it though.Non the less, you can always add material by element modifier on top of the object and set it to random ID.