Thanks for your answer, bartonc.
Well, this certainly works as a general method, though for the particular problem that motivated my question I would rather generate random numbers and check if they have the required property:

x=choice(aList)

while not property(x):

x=choice(aList)

return x

However, I'd bet this can be done even better. I would like to do without having to check the property several times on the same item. Your proposal does this, but at the cost of having to make the check 'i in beenYielded' several times on the same item.

As a solution to the general problem, your solution won't do bad, specially if 'YieldRandomItem' is called for only a few items of the list (which was the motivation), but I believe it's possible to do even better, may be at the cost of having random numbers of poorer quality.
One comment about your solution: the number of iterations of the 'while' loop required to yield the i'th element follows a geometric distribution, with expected time: n/(ni)
The total expected time if 'YieldRandomItem' has to run through the whole list is thus:
n/n+n/(n1)+n/(n2)+...+n
which is aproximately
n log(n)
So it takes generation of n log(n) random numbers and performing the check 'i in beenYielded' n log(n) times.
This last part takes 'n' operations for each check, which increases the total cost greatly, but the cost of a search operation 'x in aList' can be reduced to 'log(n)' if the list is replaced by a set.

May be a method in the random module that pops a random element from a set would be helpful....