É isso que você está procurando?
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
Isso lhe dará todas as combinações de 10 nomes aleatórios e 10 sobrenomes aleatórios. Altere os limites para alterar quantos nomes você deseja combinar.
