I'm not sure how a PSP appears to a PC when connected, but if it's like a big USB drive where you can see all the files on it in Windows Explorer, then foobar2000 can do this nicely, provided all your stuff is tagged correctly and you're willing to play about a bit with the titleformat script functions and bulk rename operations - basically you drop everything into a new playlist, order it the way you want by dragging the entries up/down (should be easy if most of it's already numbered or in order and you're just then adding a few more tracks), then you can tell the bulk rename option to include the playlist entry number at the start of the filename using something like:
<pre>$num(%list_index%,3). [%artist% - ][%album% - ][%performer% - ]%title%</pre>
(the 3 there says I want minimum 3 digits, e.g. 007, 048 etc.) Don't worry, you can save that string once you've tweaked it the way you want it to rename the files :p
If the songs aren't tagged properly though, you might end up getting the new number prefixed to the old filename instead of replacing :p
Doesn't the PSP read premade playlists and put the files in that order? :p