Hi
No matter what tool you are introducing into your organization it's good to have some basic Software Roll out concepts in mind while doing this. There are a lot of resources out there describing software roll out plans and although most of them describe how to introduce software in organizations with hundreds or thousands of users there are things to learn even if we are 'only' talking about a dozen or testers or so.
Some ideas that I think might fit you are:
Evangelist
Talk to testers and try to find one or two people who are more interested and enthusiastic about the Fiddler idea then the rest of your team. Give him/her/them time (payed working hours) to learn more about tool and to do a presentation about it to the other tester. Make sure it's someone that the other testers know and respect.
Pilot
Do a pilot project ( who better to be in charge of this than your Evangelist/s ) as a proof of concept. The pilot project should be limited to a small part of a system and the test should be of the nature that you can throw away if it does not work out. The pilot could be time-boxed and there should be an evaluation with the whole team afterwords. This will give your organization some experience in Fiddler and learn to avoid the big beginner mistakes. And it will, hopefully, show the rest of the testing team that Fiddler (or what ever tool you choose) is pretty cool and get excited about it.
Training
Of course you should dedicate time to do training properly. Just saying "read this easy to read document then start testing" is probably not going give much to the testers. Buy books on Fiddler. Let your Evangelist have a 2-hour "getting up and running with Fiddler" tutorial.
Incremental Roll out
Instead of going for a Big-bang approach where you tell you tester to start using Fiddler to test everything you should start with only limited number of test for the first release. And then you make some more tests for the next release, and maintain the first once. After a few releases you'll have a whole heap of stable and good tests using Fiddler. This way it won't take to much time of the tester so they can still do their other testing.
Read More
There are plenty of articles about software roll out plans on the web that can help you with this.
Hope this helps
/Jonas