Could you make a Zone Definition for the Free Shipping and use the shipping module Free Options freeoptions which would give the customer the choice for Free Shipping and the other regular shipping methods?