Seeing as the hardware inside the psp is quite limited, have you considered using a form of static recompilation instead of dynamic?
this should provide a large speed burst, with the downside being greatly reduced compatibility, although it would mean you could satisfy your goal of running mario 64 on the psp at playable speeds.