Invece di
codice:
 tutto_fr = tutto_fr.replace('AAA', 'BBB')
inserisci
codice:
x= Raw_input("")
tutto_fr = tutto_fr.replace('AAA', x*3)
Così puoi sostituire AAA con la stringa scelta da te, ripetuta 3 volte. Nel caso tu voglia evitare errori di battitura, puoi metterci un semplice controllo
codice:
if len(x) != 1:
 print "Errore"
Else: 
 tutto_fr = tutto_fr.replace('AAA', x*3)
Se invece vuoi proprio farglielo fare progressivamente, indenta tutto in un ciclo for, così:
codice:
caps=[ABCDEFGHIJKLMNOPQRSTUVWXYZ]
for x in caps:
 funzione che vuoi eseguire prima
  tutto_fr = tutto_fr.replace('AAA', x*3)
Ciao