>> Not all the sequences have a .pop() method.
> Not all sequences support indexing or item assignment either:

All the sequences support indexing and len(), but not assignment (e.g. tuples and strings are sequences, but they are immutable).  So talking about sequences there is incorrect (see also http://docs.python.org/py3k/glossary.html#term-sequence ).

> So seq[random] should test for random behaviour, not that indexing of
> seq itself works correctly. Similarly, seq.pop(random) should test for
> random behaviour and not for a working seq.pop()?

The test should check the behavior of the function, and in this case it includes both getting a random element and removing it.  The test doesn't have to check that seq.pop() is working fine (there are other tests for that) but that it's actually called and that it pops the right element from the input sequence (and not e.g. from a copy of the sequence that might have been created at some point).
In general it's always better to have a test more than one less.

Regarding the function itself, I'm not sure about its usefulness.  While I've used random.choice several times, I never felt the need of popping the elements.  One use case I might think of is picking all the elements of a sequence until there are no more left, without risking to pick the same element twice.  The same result can be achieved by shuffling the sequence and iterate over the elements though (that doesn't actually leave you with an empty sequence, but that's probably just a unimportant side-effect).