You can add an extra integer column to your table. Select two (using LIMIT) random items where you order the query by MIN(extra column) first, and RAND() second. After using the selected two, increment the extra field.
SELECT * FROM table ORDER BY MIN(extra), RAND() LIMIT 2
Now you get two results. For each of them, increment the extra column by 1. Next time, using the same query, you will get two different results. Suppose you have six items in the table, after the third query, all values in the extra column are set to 1, so all options are equally available again.