This can be done by configuring a Shopping Cart Price Rule, so you were definitely on the right track.
Create a new rule by going to Promotions -> Shopping Cart Price Rules -> Add New Rule. While editing your rule:
Click the "Conditions" tab. Click on ALL and change this option to ANY. For each shipping method that you would like to apply free shipping to, click the green circle to add a new condition and select "Shipping Method" followed by the specific method that you would like to make free.
Click on the "Actions" tab and change the "free shipping" option to
"For Shipment With Matching Items".You will likely need to change a few more fields in the "Rule Information" tab such as the duration of this promotion, sites, customer groups, etc.
Hope this helps. Let me know if there is anything I can clarify.