Czy tego właśnie szukasz?
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
To da ci wszystkie kombinacje 10 losowych imion i 10 losowych nazwisk. Zmień limity, aby zmienić liczbę nazw, które chcesz połączyć.