Can tower clear aircraft for take off with traffic still on the runway?
According to the ATC orders controllers can indeed clear an aircraft for takeoff 'early':


  3−9−5. ANTICIPATING SEPARATION  
  
  Takeoff clearance needs [sic] not be withheld until prescribed separation
  exists if there is a reasonable assurance it will exist when the
  aircraft starts [sic] takeoff roll.


A common scenario would be clearing an aircraft that's holding off the runway to take off while the landing aircraft is still on the runway. If the controller expects that the landing aircraft will be off the runway by the time the holding one turns onto it, then it would be allowed.

Section 3-9-6 lists the conditions for allowing an aircraft to start its takeoff roll. It's too long to quote here and you can read it yourself but the two main  conditions seem to be:


The other aircraft has departed and crossed the runway end or turned to avert any conflict
A preceding landing aircraft is clear of the runway