I'm not quite shure how they solved it in cycles renders' 'object info node'. But i think it gives a value from the position in 3d-space for each object or instance. I think, it's a pretty decent solution. Even though i like your suggestion to make use of noise as well.