"Confused Digger" algorithm running too slow, any way to speed it up?

I have an algorithm that was based on a backtracking maze algorithm with some parts removed, resulting in this wonderful dungeon. Unfortunately, it runs extremely slowly which makes it almost impossible to fill a decently-sized map with. I really don't want to throw it out, but I can't think of any way to speed it up. I'm using Python, so I know that's part of my problem, but I'm not exactly prepared to throw out my roguelike's entire existing codebase, which runs fast enough right now. Here's the code currently:

    start = (random.randint(0, self.width), random.randint(0, self.height))
    self.dungeon['up_stairs'] = start

    visited = [start]
    while len(visited) < 300:
        current = visited[-1]
        apos = random.choice([(1, 0), (0, 1), (0, -1), (-1, 0)])
        new = utils.tuple_add(current, apos)
        if not new in visited and self.on_map(new):
            self.place_cell(new, is_wall=False)
            visited.append(new)
        else:
            visited.pop()

[edit]

1. To answer some questions in the comments, place_cell either creates a wall or an empty cell at the supplied position-tuple based on the positional argument is_wall. So for instance, in the code above, the self.place_cell(new, is_wall=False) call changes the cell at the position new on the map to an empty cell.
2. Visited should really be called something else, I'm just... lazy that way. I'll fix it later probably.
3. The < 300 condition is because 299 cells is the most it can draw in a reasonable time frame. (Beyond 299 cells, it suddenly starts hanging.)

I would suggest following improvements:

• Do not pop a visited cell only because you failed on one step. This may lead to starvation: popping and trying again, popping ... etc. You should instead pick another cell you visited in the past, and continue from there. If that fails, pick another one...

• Use a set to keep track of the visited cells: this will allow faster lookup

• Use another "frontier" set for keeping track of which visited cells still have unvisited neighbours

• When a cell is visited, check all neighbours in random order whether they are unvisited. The first one that is will be your next visit. But if all of them were visited (or outside the grid) then choose a random cell from the frontier set.

Here is the suggested code:

start = (random.randint(0, self.width-1), random.randint(0, self.height-1))
self.dungeon['up_stairs'] = start

current = start
frontier = set()
visited = set([start])
while len(visited) < 400:
    frontier.add(current)
    self.place_cell(current, is_wall=False)
    found = False
    while not found:
        choices = [(1, 0), (0, 1), (0, -1), (-1, 0)]
        random.shuffle(choices)
        for apos in choices:
            new = utils.tuple_add(current, apos)
            if not new in visited and self.on_map(new):
                found = True
                break
        if not found:
            # we can remove this cell from frontier as it is 
            # completely surrounded by visited cells
            frontier.discard(current)
            # pick a random other one to start from
            current = random.sample(frontier, 1)[0]
    current = new    
    visited.add(current)