I think that this project is spectacular. So much so that I just had to register to post this comment.
I know what's wrong - why it doesn't work.
As is the case with many embedded CPUs, a small operating system is required to get the chip to do anything useful. In the case of the Nintendo 64, the operating system checks to see if a cartridge is connected and, if one is, starts loading the game by coping the program's data into RAM and jumping to the code for execution.
I'm almost 100% confident that N64s ship with stock NEC VR4300-100s (with a Nintendo branded logo on), as you have suspected, but you're going to have to rip the firmware out of the old chip and flash it to the new one.
If you look at the datasheet you've provided, you can see that the chip has a JTAG bus (JTDI, JTDO, JTCK, etc.) This is exceedingly convenient and will make this process easy. If you've had experience ripping firmware from CPUs before, you are at a major advantage. If not, no sweat. It's not that difficult, you just need the right tools. If you're interested in carrying this further, get yourself some JTAGing software, a JTAG programmer, connect the pins on the programmer to the respective pins on the CPU, and see if you get anything out of the chip. If not, there may be some enable line hiding somewhere that you may have to tie to 5v. You're going to have to use an unmodified N64 for this, as there's no way you're going to get the chip you removed powered up properly (or at least you shouldn't waste your time trying to get it to.) Make sure that when you're JTAGing you don't have any expansion pack inserted in the N64.
Once you've successfully ripped the firmware from an unmodified N64, getting it onto the modified one should be a breeze. Just do the process backwards. Feel free to email me if you have any questions. I'd love to see this work out. (My email is sonyqrio(at)me(dot)com).
Also, hey public-pervert. It's me, SonyQrio, from ModRetro.