Easily replace clips in Premiere Pro
Go to File > Project Manager.
Select the problem sequence.
In the "Resulting Project" menu, select "Collect Files and Copy"
In its options, select "Exclude Unused Clips" and unselect everything else.
Pick your destination path (not the drive where your .avi are located).
Press OK and start the copying process.


Once the copy is done, select all these files (they are all avi.) and transcode them to whatever you want, without changing their names. That supposes that you are going to export these transcoded files to a different folder than the one where your newly copied .avi files are located.

Once the transcode is done, put a dash in front of the folder in which you copied the original .avi files. 

Boot up your Premiere project. The program will ask you to reconnect the missing media. Direct it towards the folder where you put the transcoded .avi files. Because you didn't change the files' names, you'll have no trouble reconnecting your sequence to the newly converted files. No more .avi.