what I ended up doing is in app/design/frontend/default/theme_name/template/catalog/product/list_random.phtml
doing something like:
<?php
$_categories=$this->getCurrentChildCategories();
$_category = $this->getCurrentCategory();
$subs = $_category->getAllChildren(true);
$result = array();
foreach($subs as $cat_id) {
$category = new Mage_Catalog_Model_Category();
$category->load($cat_id);
$collection = $category->getProductCollection();
foreach ($collection as $product) {
$result[] = $product->getId();
}
}
shuffle($result);
?>
this will get you an array of product id's. You can loop through them and create products on the fly using:
<?php
$i=0;
foreach ($result as $_product_id){
$i++;
$_product = new Mage_Catalog_Model_Product();
$_product->load($_product_id);
//do something with the product here
}?>
then, create a static block in the cms with the following content
{{block type="catalog/navigation" template="catalog/product/list_random.phtml"}}
Finally, in the Catalog->Manage categories section, choose the category, then the display settings tab. Switch the display mode to "Static block and products" and then choose your block from the drop list.
And that should do it.