Randomly replace elements in a dictionary lists based on another list

It looks like a game but I need this to evaluate a model I'm working on. Need some help... I have a dictionary with lists as values. I need to replace only one element in each list at a random position with an element in my_list but which is not present in the list. Then I need to print which letters were swapped preferably as a list of tuples showing each key from the original dictionary. My code so far, which doesn't work as needed...:

my_list=[['a','b','c','d','e','q'],['f','j','k','l','m','n'],['o','p','r','s','t','k'], ['e','s','w','x','h','z']]
my_dict = {0:['a','d','f'], 1:['o','t','e'], 2:['m', 'j', 'k'],3:['d','z','f']}
all_letters = set(itertools.chain.from_iterable(my_list))

replace_index = np.random.randint(0,3,4)
print(replace_index)
dict_out = my_dict.copy()
replacements = []
for key, terms in enumerate(my_list):
    print(key)
    print(terms)
    other_letters = all_words.difference(terms)
    print(other_letters)
    replacement = np.random.choice(list(other_letters))
    print(replacement)
    replacements.append((terms[replace_index[key]], replacement))
    print(replacements)
    dict_out[replace_index[key]] = replacement
    print(dict_out)
print(replacements) # [(o,('a','c')...]