If item "foo" gets written as the first item in the file at iteration $N and then as the last item in the file at iteration $N+1, then "foo" will be returned twice in a row, which violates 'If I chose "foo" recently, I shouldn't use it again.'

My method of doing this is to permute the list and store it (probably in a database). When I need a new item, I pick a random number ($R) between 0 and $N where $N is a fraction of the size of the list and pick the $R'th least recently used item and mark it as the most recently used item.

One way to record which was most recently used is to put a timestamp in the records in the DB. Then picking the $R'th least recently used item can be done with a simple SQL query using "ORDER BY lastused LIMIT $R,1" (or the equivalent supported by your particular DB) and marking that item "most recently used" is a simple update to the timestamp.

The initial permutation of the list can be done by assigning each timestamp to a random time of day "yesterday".