from collections import defaultdict

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


d = defaultdict(list)
for k_outer, v_outer in main_dict.items():
    for k_inner, v_inner in v_outer.items():
        d[k_inner].append([k_outer, v_inner])

for k, v in d.items():
    print k
    print v
    print

key3
[['C', 'valueC3'], ['B', 'valueB3']]

key2
[['A', 'valueA2'], ['B', 'valueB2']]

key1
[['A', 'valueA1'], ['C', 'valueC1']]