Това ли търсите?
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
Това ще ви даде всички комбинации от 10 произволни собствени имена и 10 произволни фамилни имена. Променете ограниченията, за да промените колко имена искате да комбинирате.