Magento 1.9 Product Collection – Custom Sorting Based on Position, Best Seller, and Created Date

you cannot modify the attribute created_at in the backend.
So you need to create a module that just activates the created_at attribute for sorting.

For this you will need the following files:

app/etc/modules/[Namespace]_[Module].xml - the declaration file

<?xml version="1.0"?>
<config>
    <modules>
        <[Namespace]_[Module]>
            <codePool>local</codePool>
            <active>true</active>
            <depends>
                <Mage_Catalog />
            </depends>
        </[Namespace]_[Module]>
    </modules>
</config>

app/code/local/[Namespace]/[Module]/etc/config.xml - the configuration file

<?xml version="1.0"?>
<config>
    <modules>
        <[Namespace]_[Module]>
            <version>1.0.0</version>
        </[Namespace]_[Module]>
    </modules>
    <global>
        <resources>
            <[namespace]_[module]_setup>
                <setup>
                    <module>[Namespace]_[Module]</module>
                    <class>Mage_Catalog_Model_Resource_Setup</class> <!-- Make sure you use this class for setup -->
                </setup>
            </[namespace]_[module]_setup>
        </resources>
    </global>
</config>

app/code/local/[Namespace]/[Module]/sql/[namespace]_[module]_setup/install-1.0.0.php - the install script

<?php
$this->updateAttribute('catalog_product', 'created_at', 'frontend_label', 'Date Added'); //Set a label to the attribute because by default it does not have one
$this->updateAttribute('catalog_product', 'created_at', 'used_for_sort_by', '1'); //mark the attribute as used for sorting.

Clear the cache and refresh any page. Now you should have the Date Added (created_at) attribute available for sorting in any category.

Ok. I should wait an hour more before posting a question.
This seams to work.
I've rewritten Mage_Catalog_Model_Resource_Product_Collection::addAttributeToSort() and made it look like this (not a pretty code but works, layered navigation and all):

<?php
class Namespace_Catalog_Model_Resource_Product_Collection
    extends Mage_Catalog_Model_Resource_Product_Collection {
    public function addAttributeToSort($attribute, $dir = self::SORT_ORDER_ASC){
        //don't screw up the admin sorting.
        if (Mage::app()->getStore()->getId() == Mage_Core_Model_App::ADMIN_STORE_ID){
            return parent::addAttributeToSort($attribute, $dir);
        }
        if ($attribute == 'position') { //if should sort by position
            $newLimit = SOME code to get the limit date for products added after X days;
            $this->addExpressionAttributeToSelect(
                'sort_position',
                "(CASE WHEN {{created_at}} >= '{$newLimit}' THEN 0 ELSE 1 END)",
                array('created_at'=>'created_at')
            ); //select a 0|1 flag field. If the product is new then it has the value 0 else it's 1
            $this->addExpressionAttributeToSelect(
                'discount',
                '(CASE WHEN (price_index.price - price_index.min_price) > 0 THEN 1 ELSE 0 END)',
                array()
            );// select a 0|1 flag field. If the product has a discount then 1 else 0
            $this->getSelect()->order(array('sort_position '.$dir, 'discount '.$dir)); //sort by my new fields keeping the direction selected by the user
            return $this;
        }
        else { //if should sort by something else let Magento do it's magic.
            return parent::addAttributeToSort($attribute, $dir);
        }
    }
}