File format with per face colors
Short answer: 


.x3d, an xml based format. Color can be either specified 


per vertex of face
per face ( colorPerVertex='false' )   


When imported via Blender's importer either method get converted to a per vertex  per face scheme for the vertex_color layer.
Stanford .PLY format. (vertex colours are shared over all faces that use the vertex, only way to get color-per-face with this format is  wasteful duplication of each vertex)


or

homegrown code: essentially this code. all you need to write is the part where you map the current polygon.index to a color, so all vertices of that loop are assigned the same colour.

Take a cube.

import bpy

indexed_colors = [
    (1,0,0), (1,1,0), (1,0,1), 
    (0,0,1), (0,1,1), (0,1,0)]

obj = bpy.data.objects['Cube']
mesh = obj.data

# you probably know how to create the color layer..
if not mesh.vertex_colors:
    # creates one 'Col' by default
    obj.data.vertex_colors.new()

color_layer = mesh.vertex_colors['Col']

i = 0
for poly in mesh.polygons:
    # print(poly.loop_indices)
    color = indexed_colors[poly.index]
    for idx in poly.loop_indices:
        # loop = mesh.loops[idx]
        # v = loop.vertex_index
        color_layer.data[i].color = color[:3]
        i +=1




More elaboration on mesh generation is here: How to create a mesh programmatically, without bmesh?

from_pydata (docs link) :

mesh = bpy.data.meshes.new("mesh_name")
mesh.from_pydata(vertices=[], edges=[], faces=[])
mesh.update()

obj = bpy.data.objects.new("obj_name", mesh)

scene = bpy.context.scene
scene.objects.link(obj)


Showing vertex colors



For both methods you still need to configure the Object's material once imported, if you want it to show the vertex_color layer. This configuration is relatively painless but slightly different depending on which render engine you intend to use.

For Cycles you use a node based material, shown here

For Blender's Internal renderer the process is covered here