main_dict = {
    'A' : {'key1' : 'valueA1', 'key2' : 'valueA2'},
    'B' : {'key2' : 'valueB2', 'key3' : 'valueB3'},
    'C' : {'key3' : 'valueC3', 'key1' : 'valueC1'}
    }

print sorted([(k2, [k1, v2]) for k1, v1 in main_dict.items() for k2, v2, in v1.items()])

[('key1', ['A', 'valueA1']), ('key1', ['C', 'valueC1']), ('key2', ['A', 'valueA2']), ('key2', ['B', 'valueB2']), ('key3', ['B', 'valueB3']), ('key3', ['C', 'valueC3'])]