Ваша логика верна.Единственное, что вам нужно, это сформировать список, а не печатать результаты напрямую.
Если вы настаиваете на вложенных циклах (это домашняя работа, верно?), Вам нужно что-то вроде этого:
list1 = ["a", "b", "h", "g", "e", "t", "w", "x"]
list2 = [("a", "yellow"), ("h", "green"), ("t", "red"), ("w", "teal")]
result = [] # an empty list
for letter1 in list1:
found_letter = False # not yet found
for (letter2, color) in list2:
if letter1 == letter2:
result.append((letter2, color))
found_letter = True # mark the fact that we found the letter with a color
if not found_letter:
result.append((letter1, 'null'))
print result