いつもは適当に100件ぐらいのデータを取得して、PHPとかでランダムに配列へ格納する
なんてことをやってたんですが、MySQLでできたみたいです。

割と長くMySQLを使っていますが、全然知りませんでした。

SELECT * FROM table WHERE id > 0 ORDER BY rand() LIMIT 100;

レスポンスが遅くならないようにインデックスも含めた方がよさそうです。
う～ん、なんて便利なんだ。（早く気付けよzz）