Edit an object's material in Blender using python

Yes, you can. You will need a second material and then assign that material to the face. Here is an example I concocted which affects the faces you have selected in EDIT mode:

import bpy
import bmesh

def get_other_material():
    mat = bpy.data.materials.get("pants")
    if mat is None:
        mat = bpy.data.materials.new("pants")
        mat.diffuse_color = (0.8, 0.6, 0)
    return mat

def setPolyMaterial(obj, polyIdxs):
    if len(obj.data.materials)<2:
        obj.data.materials.append(get_other_material())
    material_index = 1

    if bpy.context.mode == 'EDIT_MESH':
        bm = bmesh.from_edit_mesh(obj.data)    
        for idx in polyIdxs:
            bm.faces[idx].material_index = material_index
        bmesh.update_edit_mesh(obj.data)
    else:
        for idx in polyIdxs:
            obj.data.polygons[idx].material_index = material_index

obj = bpy.context.active_object
if bpy.context..mode == 'EDIT_MESH':
    bm = bmesh.from_edit_mesh(obj.data)
    polyIdxs = [ f.index for f in bm.faces if f.select ]
else:
    polyIdxs = [ p.index for p in obj.data.polygons if p.select ]
setPolyMaterial( obj, polyIdxs)

I personally prefer to avoid anything from bpy.ops if I can because it requires you to mess with the editor state; and exactly what state you must adjust is entirely undocumented (although usually straightforward, USUALLY).

If you want to alter anything other than the diffuse_color, you can hover your mouse over the field and a pop-up will usually appear giving you an indication of the path to that property in python code (although sometimes it is truncated and you have to go to #blenderpython for an answer)