1) Declare a setup resource and a module version to trigger the setup workflow for a module:
<config>
<Your_Module>
<version>0.1.0</version> <!-- whatever -->
</Your_Module>
<global>
<resources>
<your_module_setup>
<setup>
<module>Your_Module</module>
</setup>
</your_module_setup>
</resources>
</global>
</config>
2) Create an install script Your/Module/sql/your_module_setup/install-0.1.0.php which (as a matter of style) uses the customer/setup class:
$installer = Mage::getResourceModel('customer/setup','customer_setup');
/* @var $installer Mage_Customer_Model_Resource_Setup */
$installer->startSetup();
//Proposed edit is correct: entity is customer_address not customer
//$installer->updateAttribute('customer','telephone','is_required',false);
$installer->updateAttribute('customer_address','telephone','is_required',false);
$installer->endSetup();
Clear the config cache, hit any page, and this should update the attribute param.