Que tal agora:
SELECT *
FROM users
ORDER BY RAND()
HAVING RAND() * 1000 < 10
A cláusula
WHERE RAND() * 1000 < 10 escolhe aleatoriamente incluir cada linha com uma probabilidade de 1%. Não é bem uma LIMIT variable cláusula, mas fará aproximadamente a mesma coisa. 
