Can a material be keyframed on a per-object basis?
You can get a random value that is unique to each object using the Object Info node.



You can also use a math node if you want to add the random value to a keyframed value change. The random value will be between 0.0 and 1.0 so you may also find multiplying helpful if you want a larger range.