Why is this query so slow?
A few places I would expect to start.  Please look at query plans but my guess is that this is a pretty simple case here of antijoins performing poorly (yes, I have been bitten by something similar even on PostgreSQL so I don't think this is unique to MySQL though InnoDB has some design decisions which make me think this could be particularly bad there).

In general, one of the basic problems  with NOT IN is that most db's I have seen end up doing this as a nested loop check using one means or another.

The first thing you should do is rewrite this as an outer join (for example a left join):

SELECT q.id
FROM questions q 
LEFT JOIN user_quiz_questions u 
          ON (u.question_id = q.id 
              &amp;&amp; user_id = ? &amp;&amp; chapter_id = ?)
WHERE 
      q.chapter_id = ? 
      &amp;&amp; (q.module = 1 || q.module = ?)
      &amp;&amp; q.question_type != 4 
      &amp;&amp; u.question_id IS NULL
ORDER BY RAND() 
LIMIT ?


The planner has a lot more freedom for how to address this and left joins are far more mature in MySQL than are subselects making me suspect that this will perform much better.

Edit:  As has been pointed out to me, this may be a misreading of your question.  Are you saying you have 2000 questions or 300000 seen questions plus 2000 questions that haven't been seen yet?  These are big differences and you are likely to need an index on join fields anyway if you don't have one.