sorry it took me so long to reply I forgot about you!
I've seen a 5VZ installed in place of the 3VZ but its more work than you think and IMO not worth it, if it were me I'd just get rid of it I know that doesn't sound like I'm much of a tech but in this case the 90-95 4-runners were the second worst vehicle toyota made because of the engines (next to the 87-90 tercels "entire car") the new HGs from toyota do hold up better but imo they just missed on the design from the get go. I'm thinking you might want to get out from under the truck because you already have transmission codes in it as well so the trans might not be far behind from letting go.
I'm not aware of what changes or differences there are between the jap version 3VZ and the US version so I can't help you there.
If you are going to do the HGs then sell it (which I'd do but thats me) the heads normally come off as a pair with the crossover pipe in the back holding them together but in your case since you have the headers it may be easier to just yank whatever side is leaking and fix it. If you do this be sure and go to the dealer and get the small pigtail wire for the knock sensor that is underneath the intake and replace it or else YOU WILL HAVE A CHECK ENGINE LIGHT AFTERWARDS. (they crack and loose connectivity)
I added downey longtube headers once to a 4-runner like yours and to me it seemed easier (faster) to bolt the header on each head then slide it in the engine compartment.