実際には、辞書を参照するためのキーは必要ありません。@mgilson が提案したように、itertools.combinations を使用して、辞書の値を直接比較できます。
>>> from itertools import combinations
>>> d = {random.randint(1,100):i for i in range(10)}
>>> list(combinations(d.values(), 2))
[(7, 4), (7, 2), (7, 3), (7, 1), (7, 0), (7, 8), (7, 9), (7, 5), (7, 6), (4, 2), (4, 3), (4, 1), (4, 0), (4, 8), (4, 9), (4, 5), (4, 6), (2, 3), (2, 1), (2, 0), (2, 8), (2, 9), (2, 5), (2, 6), (3, 1), (3, 0), (3, 8), (3, 9), (3, 5), (3, 6), (1, 0), (1, 8), (1, 9), (1, 5), (1, 6), (0, 8), (0, 9), (0, 5), (0, 6), (8, 9), (8, 5), (8, 6), (9, 5), (9, 6), (5, 6)]
>>>