Je to to, co hledáte?
SELECT *
FROM (
SELECT firstname
FROM firstnames
ORDER BY RAND( )
LIMIT 10
) AS tb1
JOIN (
SELECT lastname
FROM lastnames
ORDER BY RAND( )
LIMIT 10
) AS tb2 ON 1=1
Tím získáte všechny kombinace 10 náhodných křestních jmen a 10 náhodných příjmení. Změňte limity a změňte počet jmen, které chcete zkombinovat.