nombres-aliases.py

import pandas as pd

# El dataframe de ejemplo
df = pd.DataFrame(
    {'A':['toto', 'titi', 'tete', 'tete', 'titi', 'toto'],
     'B':["ayer titi vio a toto", "Hola tete", "bye", "tititete", " ", "tite"]}
)

# La lista de todos los personajes de Cancion de Hielo y Fuego
got_dt = pd.read_csv("https://raw.githubusercontent.com/mathbeveridge/asoiaf/master/data/asoiaf-all-nodes.csv")

# Obtiene nombres y aliases
nombres = list(df.A.unique())
aliases = list(got_dt.Label.sample(len(nombres)))

# Remplaza en la columna A nombres por aliases por entrada completa
df.A.replace(nombres, aliases, inplace=True)

#Remplaza en la columna B en cada entrada en forma de string (por partes)
for (nombre, alias) in zip(nombres, aliases):
    df.B = df.B.str.replace(nombre, alias)

Acabo de ver que puse Cancion, y no Canción :-(