AVI with multiple audio tracks is something of a hack as far as I am aware. Likewise I am not so familiar with the PSP video requirements beyond certain res and some flavour of MP4 but chances are you want to remux the audio tracks (both AVI and MP4 are quite easy to mess around with) into a new MP4. I do not believe the PSP supports multiple audio tracks so you will have to make a choice (or make two videos I guess).
This is a really easy process for a system to do and it will probably only be limited by your hard drive (if you have the files in front of you and it takes more than 30 seconds for a video less than three hours long something has gone very wrong).
Tools to do the deed-
MP4box with frontends in tools like YAMB or My MP4Box GUI
http://www.videohelp.com/tools/MP4Box
http://www.videohelp.com/tools/YAMB
http://www.videohelp.com/tools/My-MP4Box-GUI
YAMB can do a lot with AVI as can many other tools, however there are simpler tools alongside more fully featured ones like
http://fixounet.free.fr/avidemux/ and virtualdub.
Depending upon how the PSP works and what was used in the AVI you might have to convert the audio again but that is not a hard task should it come to it.