How to add empty object not using bpy.ops?
This is possible by placing None as the object data:

#                          Name,   Data
o = bpy.data.objects.new( "empty", None )
bpy.context.scene.objects.link( o )


You can later access its unique empty props like any ol' empty:

o.empty_draw_size = 2
o.empty_draw_type = 'PLAIN_AXES'


For Blender 2.8, the API change a little bit:

o = bpy.data.objects.new( "empty", None )

# due to the new mechanism of "collection"
bpy.context.scene.collection.objects.link( o )

# empty_draw was replaced by empty_display
o.empty_display_size = 2
o.empty_display_type = 'PLAIN_AXES'