I've written up a fairly simple class for you and will detail the usage afterwards
from random import random
from math import floor
class FairDice():
    def __init__(self, sides = 6):
        self.sides = sides
        self.history = []
        self.last = None
    def roll(self):
        number = random()
        roll = int(floor(number * self.sides)) + 1
        return roll
    def statefull_roll(self, remember = None):
        while True:
            roll = self.roll()
            remember = self.sides if remember is None else remember
            if len(self.history) >= remember:
                return None
            if roll not in self.history:
                self.history.append(roll)
                return roll
    def forget_history(self):
        self.history = []  
    def forget_one(self):
        self.history = self.history[1:]
I've created this FairDice class. You can do regular rolls by calling .roll() function. Or you can do rolls that remember what has been rolled by calling the statefull_roll() method. If there are no numbers left then None is returned. You can also call the forget_history() function to forget history.  
Here is an example of usage:  
dice = FiarDice(25) #creates a 25 sided dice  
for x in range(10):
    print("Regular Roll gives you: ", dice.roll())  
for x in range(25):
    print("Your sort of Roll gives you: ", dice.statefull_roll()) 
print ( dice.statefull_roll()) # Should return none after exhausting all possible characters. 
dice.forget_history() # forgets that any value have been recorded at all  
Lets say that it's ok to repeat letters after 5 rolls. I've added the none.    
roll = dice.statefull_roll(remember = 5)  
This will return None after 5 rolls after which all you have to do is...
if roll is None:
    dice.forget_one()  
    roll = dice.statefull_roll(remember = 5)  
forget_one forgets your oldest roll.  
What I've written is not much, but works and is flexible enough for usage in your game.