sorted(enumerate([('a', 1), ('b', 2)]), key=lambda (i, (k, v)): (k, i, v))
You could do this, although it's admittedly uglier than your example:
In [1]: sorted(enumerate([('b', 1), ('c', 3), ('a', 2)]), key=lambda x: (x[1][0], x[0], x[1][1]))
Out[1]: [(2, ('a', 2)), (0, ('b', 1)), (1, ('c', 3))]
In [1]: sorted((x, i) for i, x in enumerate([('b', 1), ('c', 3), ('a', 2)]))
Out[1]: [(('a', 2), 2), (('b', 1), 0), (('c', 3), 1)]
but gives the wrong answer, as you'll see if you try to sort [('a', 2), ('a', 1)]