Editing the template will not work for your case. The template has a set of options which are applied when a new phone is added to an extension. In your case it is the order of the codecs. If you change those options in the template then the already added phones will not be affected by the template change, only newly added phones. They will not be affected because you do not want to apply some changes under the phone provisioning tab and have the template override those options every time.
So for already added phones the only way to change the order of the codecs is by applying the change manually under each extension and re-provisioning the phone. Multi selecting the extensions and editing them will also not work i think as the management console only allows changes to settings that are common to all extensions by default.
