MySQL Query para recibir combinaciones aleatorias de dos tablas

¿Es esto lo que estás buscando?

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

Esto le dará todas las combinaciones de 10 nombres aleatorios y 10 apellidos aleatorios. Cambie los límites para cambiar cuántos nombres desea combinar.