Fading and animating objects without materials
Ok so I figured out a solution thanks to @Carlo's comment. Hopefully this will help anyone else who's trying to do something similar.

I create one node group per object type that has a default color, and accepts one input: transparency. The node group itself is basically a mixer between Diffuse bsdf and transparent bsdf shaders. 

Each object of that type has it's own material which basically links the node group with the material output. I can then keyframe the opacity on each material independently, but still maintain the ability to change the color collectively for the type by changing the node group color.

Since I am scripting this, I am not worried about having to keyframe 5000+ objects. I came up with the following functions: 

# create_node_group - Creates a node group
# for a particle type with a default color.
def create_node_group(name, color):
    group = bpy.data.node_groups.new(name, 'ShaderNodeTree')

    # Create node group input.
    inputs = group.nodes.new('NodeGroupInput')
    inputs.location = (-300, 0)

    # Create diffuse shader.
    diffuse = group.nodes.new('ShaderNodeBsdfDiffuse')
    diffuse.location = (0, -200)
    diffuse.inputs[0].default_value = (color[0], color[1], color[2], 1)

    # Create transparent shader.
    transparent = group.nodes.new('ShaderNodeBsdfTransparent')
    transparent.location = (0, -400)

    # Create shader mixer.
    mixer = group.nodes.new('ShaderNodeMixShader')
    mixer.location = (200, 0)

    # Create node group output.
    outputs = group.nodes.new('NodeGroupOutput')
    outputs.location = (350, 0)

    # Create input and output sockets.
    group.inputs.new('NodeSocketFloat', 'Transparency')
    group.outputs.new('NodeSocketShader', 'Shader')

    # Link everything together.
    group.links.new(inputs.outputs[0], mixer.inputs[0])
    group.links.new(diffuse.outputs[0], mixer.inputs[1])
    group.links.new(transparent.outputs[0], mixer.inputs[2])
    group.links.new(mixer.outputs[0], outputs.inputs[0])

    return group


The above function creates the node group and returns a reference to it. I then use the function below to create a material for each object in my scene, which calls the function above. 

# create_material - Creates a material with a color
# for the group (if not created already). Name and
# group name should typically be the same.
def create_material(name, group_name, color):
    group = bpy.data.node_groups.get(group_name)
    if group is None:
        group = create_node_group(group_name, color)

    mat = bpy.data.materials.new(name)
    mat.use_nodes = True

    for node in mat.node_tree.nodes:
        mat.node_tree.nodes.remove(node)

    mgroup = mat.node_tree.nodes.new('ShaderNodeGroup')
    mgroup.node_tree = group

    outmat = mat.node_tree.nodes.new('ShaderNodeOutputMaterial')
    outmat.location = (200, 0)

    mat.node_tree.links.new(mgroup.outputs[0], outmat.inputs[0])
    return mat


Finally, if I want to change the opacity of an object, I simply call this small function: 

# set_transparency - Set the transparency of an object.
def set_transparency(ob, val):
    mat = ob.data.materials[0]
    mat.node_tree.nodes["Group"].inputs[0].default_value = val


This may not be the best solution, but it works for me, and hopefully it will help others in a similar situation.

Thanks!