Four Random Products on Homepage

Try this. I worked for me:

$products = Mage::getModel('catalog/product')->getCollection();
$products->addAttributeToSelect(array('name', 'thumbnail', 'price')); //feel free to add any other attribues you need.
Mage::getSingleton('catalog/product_status')->addVisibleFilterToCollection($products);
Mage::getSingleton('catalog/product_visibility')->addVisibleInCatalogFilterToCollection($products); 
$products->getSelect()->order('RAND()');
$products->getSelect()->limit(4);
foreach ($products as $product)  : ?>

<div class="three columns">
  <div class="product_container no_border">
    <div class="product">
      <a href="<?php echo $product->getProductUrl()?>"><img src="<?php echo Mage::helper('catalog/image')->init($product, 'thumbnail')->resize(100, 80)?>" alt=""></a>
    </div>

    <div class="product_title">
      <a href="<?php echo $product->getProductUrl()?>"><?php echo $product->getName()?></a>
    </div>

    <div class="price_hp"><?php echo Mage::app()->getStore()->getCurrentCurrency()->format($product->getFinalPrice());?></div>

    <div class="free_shipping">
      <div class="fs"></div>
      Free shipping for this package
    </div>

    <div class="shop_btn">
      <a href="<?php echo Mage::helper('checkout/cart')->getAddUrl($product)?>">ADD TO CART</a>
    </div>
  </div>
</div>
<?php 
endforeach;?>

Create Block For Random Products

You should create a custom module with a new block type. I'd recommend to extend Mage_Catalog_Block_Product_List, then if the default product list layout suffices for you, you don't even need to design your own template.

Then override _getProductCollection() or if you don't extend Mage_Catalog_Block_Product_list write a new public method getProductCollection().

How to prepare the product collection in this method:

Collection Filter

First, create the collection and apply the standard filter (visible in catalog and available in current store):

$productCollection = Mage::getModel('catalog/product')->getCollection();
$productCollection
    ->addStoreFilter()
    ->setVisibility(Mage::getSingleton('catalog/product_visibility')->getVisibleInCatalogIds());

Performant Random Selection

ORDER BY RAND() is unperformant on large tables because it results in a resource intensive temp table copy. It has to load all results into a temporary table, assign a random number to each row and then sort without any index. Instead we retrieve all ids (this is faster and the amount of data is managable even for large catalogs), pick some randomly and retrieve these rows directly.

To do so, insert this code after the filters for the collection have been applied:

$numberOfItems = 4;
$candidateIds = $productCollection->getAllIds();

$choosenIds = [];
$maxKey = count($candidateIds)-1;
while (count($choosenIds) < $numberOfItems)) {
  $randomKey = mt_rand(0, $maxKey);
  $choosenIds[$randomKey] = $candidateIds[$randomKey];
}

$productCollection->addIdFilter($choosenIds);

You can read about it in detail in my blog: http://www.schmengler-se.de/en/2015/09/show-random-products-in-magento-you-are-doing-it-wrong/

Retrieve Necessary Attributes

Then, we specify the attributes to be loaded and join price and URL indexes to be able to show the right price and product URL:

$productCollection
    ->addMinimalPrice()
    ->addFinalPrice()
    ->addTaxPercents()
    ->addAttributeToSelect(Mage::getSingleton('catalog/config')->getProductAttributes())
    ->addUrlRewrite();

Last but not least, return the collection:

return $productCollection;

---

This collection can now be used in Mage_Catalog_Block_Product_List blocks or in your own template with foreach ($this->getProductCollection() as $product) like in Marius' answer.

---

Insert Custom Block In CMS

Use this code to insert the block in your home page, with your/block being the alias for your block class:

{{block type="your/block" name="random_products" template="catalog/product/list.phtml" column_count="4"}}

Specify your own template if needed. column_count is used by Mage_Catalog_Block_Product_List.

---

Notes

1. Alternatively you could put all the PHP code from above in your template but this is quite messy and violates Magento's coding standards and best practices.

2. Apparently Magento comes with its own predefined block type catalog/product_list_random, but it uses order('rand()'), so I won't recommend it for the performance reasons explained above.