I would go with a Widgetized footer.
If you want to go the extra mile, rather than create Theme Options, simply create a custom Widget, e.g. Footer Contact Details, that has editable text inputs for Company Name, Address Lines 1 and 2, Phone/Fax, and Email.