Try to get the product collection like this:
$_productCollection = Mage::getResourceModel('reports/product_collection')
->addAttributeToSelect('*')
->addCategoryFilter($_category)
->setVisibility(array(2,3,4));
Mage::getSingleton('cataloginventory/stock')->addInStockFilterToCollection($_productCollection); //this should filter in stock products only
$_productCollection->getSelect()->order(new Zend_Db_Expr('RAND()'));
$_productCollection->setPage(1, 4);