What is the most efficient way to exclude records with a particular ID in a MySQL query for random records?
I'm avoiding using RAND() because it has been said it doesn't work for large tables. I wonder how large is large? 


As for "doesn't work", I say that is false.  RAND() does not repeat after 64K, like some random number generators.

As far as "how large", time the first query below -- if it is "too slow" then the table is "too large".  Then skip to the link at the bottom.

Case 1 Done all at once, this gives you $N random, not repeated, rows:

$array = SELECT id FROM ... WHERE ... ORDER BY RAND() LIMIT $N;


Case 2 If you need to fetch the rows individually, such as with separate requests and minimal "memory" between requests:

$rnd = UNIX_TIMESTAMP();
$offs = $offs + 1;
$array = SELECT id FROM ... WHERE ... ORDER BY RAND($rnd) LIMIT $N OFFSET $offs;


By remembering $rnd and $x (eg passing via a URL or SESSION), you can get the "next" one in a predictable sequence.

Caveat 1:  If rows are inserted/deleted, this sequence can mess up.
Caveat 2:  If the table is 'large', the SELECT could be costly.

8 Faster ways to get random rows.  None is 'perfect', and each depends on something not in evidence, such as whether there is an auto_increment id and whether that has gaps.