Instantiating objects and applying different material to them
Both the Object and Mesh classes actually have place to store materials. For object it is Object.material_slots and Mesh.materials. This means that Mesh always has their own "default" materials but they could be overridden on Object level. I don't know the origin of this but it comes in handy.

Normally the settings are paired but to override material per object, you need to set the object's material slot from "DATA" to "OBJECT". This makes Blender store the material per object instead of reading it from the mesh data. It is easiest to set this up for the source Object, all clones will inherit this setting afterwards.



In python you can set this via.

object.material_slots[i].link = 'OBJECT'


After you make the change, you need re-assign the material slot as setting this clears any reference.

Here are links to official Blender python API in case you want to dig around some more: 
https://docs.blender.org/api/current/bpy.types.Mesh.html?highlight=materials
https://docs.blender.org/api/current/bpy.types.Object.html?highlight=material_slots

Depending on your case though, if you only want simple color variation instead of having completely different materials, it might be better way to set up your material so that you get a random per object color using Object Info > Random and color ramp for example. Or Object Info > Location plugged into textures like Musgrave or Voronoi for patterned variance.