What is the most pythonic way to pop a random element from a list?

You won't get much better than that, but here is a slight improvement:

x.pop(random.randrange(len(x)))

Documentation on random.randrange():

random.randrange([start], stop[, step])
Return a randomly selected element from range(start, stop, step). This is equivalent to choice(range(start, stop, step)), but doesn’t actually build a range object.

What you seem to be up to doesn't look very Pythonic in the first place. You shouldn't remove stuff from the middle of a list, because lists are implemented as arrays in all Python implementations I know of, so this is an O(n) operation.

If you really need this functionality as part of an algorithm, you should check out a data structure like the blist that supports efficient deletion from the middle.

In pure Python, what you can do if you don't need access to the remaining elements is just shuffle the list first and then iterate over it:

lst = [1,2,3]
random.shuffle(lst)
for x in lst:
  # ...

If you really need the remainder (which is a bit of a code smell, IMHO), at least you can pop() from the end of the list now (which is fast!):

while lst:
  x = lst.pop()
  # do something with the element      

In general, you can often express your programs more elegantly if you use a more functional style, instead of mutating state (like you do with the list).