I don't know about speed, but this seems to work:
SELECT url
FROM
( SELECT url, domain
FROM tbl
ORDER BY RAND() ) y
GROUP BY domain
ORDER BY NULL
LIMIT 1000;
Example:
mysql> SELECT city, state FROM
-> ( SELECT city, state FROM us ORDER BY RAND() ) y
-> GROUP BY state
-> ORDER BY NULL
-> LIMIT 11;
+-----------------+-------+
| city | state |
+-----------------+-------+
| Gardiner | ME |
| Flossmoor | IL |
| Burke | VA |
| Sulphur Springs | TX |
| Festus | MO |
| Garden Grove | CA |
| Bergenfield | NJ |
| Hanover | MA |
| Loudon | NH |
| Plymouth | CT |
| New Castle | IN |
+-----------------+-------+
11 rows in set (0.06 sec)
mysql> SELECT city, state FROM
-> ( SELECT city, state FROM us ORDER BY RAND() ) y
-> GROUP BY state
-> ORDER BY NULL
-> LIMIT 11;
+------------------+-------+
| city | state |
+------------------+-------+
| Lyndon | VT |
| Mount Dora | FL |
| Memphis | TN |
| Grand Haven | MI |
| Georgetown | DE |
| Stanton | CA |
| Bismarck | ND |
| Valley Station | KY |
| Dracut | MA |
| Great Neck | NY |
| North Providence | RI |
+------------------+-------+
11 rows in set (0.06 sec)