Non hai molte alternative... una tabella temporanea oppure UNION.
codice:
(select * from tab
where id_categoria = 1
order by RAND()
limit 1 )
UNION
(select * from tab
where id_categoria = 2
order by RAND()
limit 1 )
UNION
(select * from tab
where id_categoria = 3
order by RAND()
limit 1 )


Con mysql 5.0.15 potresti farci una "view" oppure una "stored procedure"