[empty_tuple] * 10000 creates a list that contains 10000 references to empty_tuple, so when you modify it with lst[77][0]=..., it will be reflected across all of l.
It's a bit tricky if you really want to use tuples, as they are immutable, but you can do something like:
>>> sett = lambda t, idx, val: tuple((v if i != idx else val) for i,v in enumerate(t))
>>> l = [(0,) * 3] * 4
>>> l
[(0, 0, 0), (0, 0, 0), (0, 0, 0), (0, 0, 0)]
>>> l[1] = sett(l[1], 2, 42)
>>> l
[(0, 0, 0), (0, 0, 42), (0, 0, 0), (0, 0, 0)]
where sett is a function that takes a tuple t, an index idx, and a value val, and returns a tuple that is identical to t in every index but idx, where it contains val.
One way to set up a list of distinct lists would be:
>>> l = map(lambda _: [0] * 3, xrange(4))
>>> l[0][1] = 2
>>> l
[[0, 2, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]