Se você não se importar com alguns dos dados da tabela não podem ser processados (depende do tamanho da tabela, espere que 50% da linha não possa ser processada), aqui está uma solução:
Tabela Original
id name
1 Some
2 Body
3 Once
4 Told
5 Me
6 The
7 World
8 Is
9 Gonna
10 Roll
11 Me
12 I
13 Ain't
14 The
15 Shapest
16 Tool
17 In
18 The
19 Shed
20 She
21 was
22 looking
23 kind
24 of
25 dumb
26 with
27 her
28 finger
29 and
30 her
31 thumb
Consulta:
SELECT new_id, name FROM (
SELECT new_id, name FROM (
SELECT new_meme.id as new_id, original_meme.id as original_id, original_meme.name FROM meme original_meme
JOIN meme new_meme ON new_meme.id <> original_meme.id
ORDER BY RAND()
) layer1
GROUP BY layer1.new_id
) layer2 GROUP BY name
Resultado (diferente a cada corrida)
1 I
2 In
3 Gonna
4 Ain't
5 The
6 her
7 finger
8 Some
9 dumb
10 She
15 Me
16 with
17 Told
18 and
19 World
21 Roll
22 The
25 Tool
26 Shed
27 Is
28 Me
29 Sharpest
31 The
Observação:você pode achar a consulta muito lenta , isso ocorre porque ele se junta à tabela duas vezes , portanto, se o tamanho dos dados for 1000, ele precisará processar 1000 * 1000.
Você pode controlar a velocidade da consulta alterando
ON new_meme.id <> original_meme.id para ON new_meme.id BETWEEN original_meme.id - 5 AND original_meme.id +5 (o 5 pode ser alterado), mas diminuirá a aleatoriedade e não funcionará para id não numérico 
