How to add item to Magento collection to the beginning?

DISCLAIMER: Use the database for sorting purposes wherever possible. However, in some cases you might want to arrange items in a collection that are not stored in the database (yet), for example after dynamically adding items to the quote during collectTotals(). Then this approach will be useful.

Unfortunately not, Varien_Data_Collection is not very flexible in this respect. To reorder items in a collection you need to remove them and add them again in the desired order.

In your specific case:

// remove previous items, keep them in $items
$items = $productCollection->getItems();
foreach ($productCollection as $key => $item) {
    $collection->removeItemByKey($key);
}

// add new item
$productCollection->addItem($product);

// re-add $items
foreach ($items as $item) {
    $productCollection->addItem($item);
}

Update: Performance

Since there are objections regarding performance, I did a little benchmark on a real product database. Note that loading a collection with 20K products is something you should never actually do but this is just to prove the point that iterating over the loaded arrays twice does not add a significant overhead:

Test Script

$startTime = microtime(true);
$productCollection = Mage::getResourceModel('catalog/product_collection')->load();

printf("Loaded %d products. Time: %.2fs Memory: %s\n",
    $productCollection->count(), microtime(true)-$startTime, number_format(memory_get_usage(true)));

// remove previous items, keep them in $items
$items = $productCollection->getItems();
foreach ($productCollection as $key => $item) {
    $productCollection->removeItemByKey($key);
}

printf("Removed items. Time %.2fs Memory: %s\n",
    microtime(true)-$startTime, number_format(memory_get_usage(true)));

// add new item
$productCollection->addItem(Mage::getModel('catalog/product'));

// re-add $items
foreach ($items as $item) {
    $productCollection->addItem($item);
}

printf("Added items. Time %.2fs Memory: %s\n",
    microtime(true)-$startTime, number_format(memory_get_usage(true)));

Output

Loaded 20761 products. Time: 3.70s Memory: 81,264,640

Removed items. Time 3.92 Memory: 81,788,928

Added items. Time 4.31 Memory: 81,788,928

And with a more realistic amount of 100 loaded products:

Loaded 100 products. Time: 0.11s Memory: 10,223,616

Removed items. Time 0.11s Memory: 10,223,616

Added items. Time 0.12s Memory: 11,272,192

A collection object has a standard array called _items which contains all the resulting models retrieved by the database query. The addItem() method exists in class Varien_Data_Collection and if you look at it all it does is push an entry onto the end of the array and is subject to exactly the same behaviour as array_push:

public function addItem(Varien_Object $item)
{
    $itemId = $this->_getItemId($item);

    if (!is_null($itemId)) {
        if (isset($this->_items[$itemId])) {
            throw new Exception('Item ('.get_class($item).') with the same id "'.$item->getId().'" already exist');
        }
        $this->_items[$itemId] = $item;
    } else {
        $this->_addItem($item);
    }
    return $this;
}

And the _addItem() method is as follows:

protected function _addItem($item)
{
    $this->_items[] = $item;
    return $this;
}

Thus all that happens when calling the addItem() method is that a new entry is added to the end of the array using the id of the item you are adding if it exists as the key, otherwise using the next available auto increment key value (by not defining a key).

If you need to have the items ordered in a specific way, you should instead ensure your database query orders the results correctly, or pull all of the item from the collection object using getItems() and then order then using PHP. By FAR the most efficient is to order them correctly in your database query, manipulating the results once pulled from the database via PHP is countless times slower.