select 1 random row with complex filtering

I've 2 tables:

first table users:

+-------------------------+---------+------+-----+---------+-------+
| Field                   | Type    | Null | Key | Default | Extra |
+-------------------------+---------+------+-----+---------+-------+
| id                      | int(11) | NO   | PRI | NULL    |       |
| first_name              | text    | NO   |     | NULL    |       |
| age                     | int(11) | YES  |     | NULL    |       |
| settings                | text    | YES  |     | NULL    |       |
+-------------------------+---------+------+-----+---------+-------+

second table proposals:

+---------+---------+------+-----+---------+----------------+
| Field   | Type    | Null | Key | Default | Extra          |
+---------+---------+------+-----+---------+----------------+
| id      | int(11) | NO   | PRI | NULL    | auto_increment |
| from_id | int(11) | NO   |     | NULL    |                |
| to_id   | int(11) | NO   |     | NULL    |                |
| status  | int(11) | NO   |     | NULL    |                |
+---------+---------+------+-----+---------+----------------+

I need to get 1 random row from users which id is not in to_id in proposals

I'm doing it (without rand) with this sql:

SELECT DISTINCT *
FROM profiles
WHERE
    profiles.first_name IS NOT NULL
AND
NOT EXISTS (
    SELECT *
    FROM proposal
    WHERE
        proposal.to_id = profiles.id
)
LIMIT 0 , 1

performance is fine: 1 row in set (0.00 sec)

but when I add ORDER BY RAND() to the end perfomance is very bad: 1 row in set (1.78 sec)

I've big holes in users.id and I can't use something like MAX(id)

How to get random 1 user which users.id isn't exists in proposals.to_id with good perfomance?

via MixerOID