Since Magento uses the Zend Framework you are able to use Zend_Date to easily display localized dates in Magento.
$date = new Zend_Date(Mage::getModel('core/date')->timestamp(time(), false, Mage::app()->getLocale()->getLocaleCode()));
echo $date->toString("EEEE, d. MMMM YYYY");
So, first create a Zend_Date object based on the locale set in the administration backend:
Mage::app()->getLocale()->getLocaleCode()
Then simply output your date as localized string using Zend_Date->toString:
echo $date->toString("EEEE, d. MMMM YYYY");
Us usual, find formating rules in the Zend_Date constants documentation.