To change the query you can do

$collection->getSelect()->doWhateverYouWantWithSelectObject();
foreach($collection as $order) {} // order collection

But to join a table, you can just use $collection->joinTable()

joinTable only exists on Mage_Eav_Model_Entity_Collection, this means: products, categories, orders, invoices, creditmemo, shipping, customers. (Thanks @Fra for the comment)

joinTable()

But magento collections have a method joinTable() it took me 45min to fizzle out how it is used. To avoid this for you, I share it.

$productCollection->joinTable(
    array('bonus' => 'mycompany/bonus'), 'product_id=entity_id',
    array('bonus_id' => 'bonus_id')
);

The parameters are:

public function joinTable($table, $bind, $fields = null, $cond = null, $joinType = 'inner')

1. Table is easy, it is the magento namespace/entity format, which you use in your configuration, resource models and the collection. You can use an array of the format array('alias' => 'namespace/entity')
2. Bind means, the ON statement in your SQL. This was the hardest part and I will explain it in details later. It is important to have your flat table BEFORE and your EAV table AFTER the equal sign. Don't use main_table. before the attribute. Magento will do this for you. More on this later.
3. Fields is an array. If you use a string instead, you get this: Warning: Invalid argument supplied for foreach() in /var/www/magento-1.6.2.0/app/code/core/Mage/Eav/Model/Entity/Collection/Abstract.php on line 775. You can use an array of the format array('field1', 'field2', '...') or array('alias' => 'field1', '...')
4. Condition is a ** WHERE ON condition** in the SQL.
5. joinType. I hope you know what it is. But you have only the choice between LEFT and INNER. app/code/core/Mage/Eav/Model/Entity/Collection/Abstract.php:793

More on this topic

The original answer is for BETWEEN. For NOT BETWEEN see update below

For the collection filter operators, it's always useful to take a look at Varien_Db_Adapter_Pdo_Mysql::prepareSqlCondition() which is well documented:

/**
 * Build SQL statement for condition
 *
 * If $condition integer or string - exact value will be filtered ('eq' condition)
 *
 * If $condition is array is - one of the following structures is expected:
 * - array("from" => $fromValue, "to" => $toValue)
 * - array("eq" => $equalValue)
 * - array("neq" => $notEqualValue)
 * - array("like" => $likeValue)
 * - array("in" => array($inValues))
 * - array("nin" => array($notInValues))
 * - array("notnull" => $valueIsNotNull)
 * - array("null" => $valueIsNull)
 * - array("gt" => $greaterValue)
 * - array("lt" => $lessValue)
 * - array("gteq" => $greaterOrEqualValue)
 * - array("lteq" => $lessOrEqualValue)
 * - array("finset" => $valueInSet)
 * - array("regexp" => $regularExpression)
 * - array("seq" => $stringValue)
 * - array("sneq" => $stringValue)
 *
 * If non matched - sequential array is expected and OR conditions
 * will be built using above mentioned structure
 *
 * @param string|array $fieldName
 * @param integer|string|array $condition
 * @return string
 */

Unfortunately there is no operator for BETWEEN, so you will have to either use $collection->getSelect() to manipulate the query directly or use a combination of < and > instead, which can be built using the from and to keys. For date comparison, there is even an additional date or datetime key that will make sure that the from and to parameters are formatted as dates¹.

But in your case, not the field itself should be "between" to parameters but the current date between two fields, so we cannot use from, to and datetime. Instead we call addFieldToFilter() twice so that the conditions are combined with AND:

->addFieldToFilter(array('start_date' => array('lt' => $curDate))
->addFieldToFilter(array('end_date' => array('gt' => $curDate));

To really use CURDATE() from MySQL and avoid trouble from timezone settings in PHP, initialize $curDate like this:

$curDate = new Zend_Db_Expr('CURDATE()');

Update:

Since you were asking for NOT BETWEEN, you need to switch lt and gt and add both conditions in a single addFieldToFilter call to combine them with OR:

->addFieldToFilter(array(
    'start_date' => array('gt' => $curDate),
    'end_date' => array('lt' => $curDate)
));

This will also find records where start_date is NULL and end_date is in the past (and vice versa), but not records where start_date and end_date are both NULL. This makes sense if start_date and end_date follow the same semantics as in core Magento and you want to find all records that are currently not within the range.

So you already were close to the solution but passed the parameters in a wrong form.

^{1) In theory, 'date' => true should format the parameter as date and 'datetime' => true as date and time. But they forgot to pass the $includeTime parameter to formatDate() in _prepareSqlDateCondition(), so they both use the default format (date and time)}