I've encountered with this problem several times in web development and every time found out that the best (in terms of performance) solution is to use some pseudo random approach (such as ">= random() limit 1" or "limit 1 offset random()*N" or even pre-caching rows on app side).