1- Remove the required class from following files in your theme folder.
checkout/onepage/shipping.phtml
checkout/onepage/billing.phtml
persistent/checkout/onepage/billing.phtml
<!--<label for="shipping:telephone" class="required"><em>*</em><?php echo $this->__('Telephone') ?></label>-->
<label for="shipping:telephone"><?php echo $this->__('Telephone') ?></label>
also remove classes from input field as-well
<?php //echo $this->helper('customer/address')->getAttributeValidationClass('telephone') ?>
2- copy this core class to your local and remove following lines
app/code/core/Mage/Customer/Model/Address/Abstract.php
/*if (!Zend_Validate::is($this->getTelephone(), 'NotEmpty')) {
$this->addError(Mage::helper('customer')->__('Please enter the telephone number.'));
}*/
3- Change the attribute is_required in DB
update eav_attribute set is_required=0 where attribute_code='telephone';
Note: step three is a dirty hack, correct way would be creating an setup file in your custom extension.