Is it possible to iterate over Magento collections with pagination natively?

You should really use

Mage::getSingleton('core/resource_iterator')

for this purpose, as it exists purely for the performance reasons you mentioned.

Otherwise, you can use a slightly less elegant solution using a loop with setPageSize - there's a good example here, https://stackoverflow.com/questions/3786826/how-to-loop-a-magento-collection

I agree with Ben Lessani that you should use the core/iterator resource model to load big collections one row at a time if possible.

However, there are limitations. As explained in "addAttributeToSelect not working with core/resource_iterator?" it does not work well with EAV models if you need to include values from the attribute value tables.

And the linked example from StackOverflow is actually not that good because it repeats the same query with different LIMIT expressions. For complex queries this might be a performance problem, but even more important, you will get duplicates if new rows are added in between.

A better way to handle collections in chunks is to first load all the ids, then use these ids as a filter for the actual paged collection.

Simple example for products:

$ids = Mage::getModel('catalog/product')
    ->getCollection()
    ->getAllIds();

$page = 1;
do {
    $collection = Mage::getModel('catalog/product')
        ->getCollection()
        ->addIdFilter($ids)
        ->setPageSize(100)
        ->setCurPage($page);

    $results = $collection->load();

    // do stuff ......

    $page++;

} while ($results->count());