The Nintendo 64 debuted in 1996 and featured a 64-bit MIPS processor. My understanding is that PCs didn't start appearing with 64-bit CPUs until 2003. What was the advantage of using a 64-bit CPU in 1996? Presumably, back then addressing more than 4GB of memory would not have been an issue for a consumer electronics device.
This is mostly content-free marketing hype. Yes, the processor may have been "64 bit" (however that is really defined), but that by itself means little. As you say, it is unlikely that addressing more than 4 Gb would have been of any use in 1996.
Presumably, a "64 bit" processor can do arithmetic manipulation on 64 bit quantities as a whole, and that could have speeded up certain operations. However, there are many other architectural choices that result in various cost versus speed tradeoffs that would have had a much larger impact on the result than whether the processor was 64 bit or 32 bit or something else. The fact that at least parts of the processor were 64 bit is therefore pretty meaningless when looked at in isolation. What really matters is the resulting performance and what price you have to pay to get it.
This is somewhat like making a big deal about whether the engine in a car has a overhead cam or dual exhaust valves, for example. That by itself tells you very little since the many other tradeoffs in the design of the car and its engine swamp the effects of that one design choice on the resulting performance and price. Just like "64 bit", these are mostly just hype because marketing thinks it sounds cool and that you're dumb enough to think it matters. Unfortunately for most consumers, marketing is right.
The use of "64 bits" was probably as much a marketing term as anything, but not entirely without meaning. On many machines of that era, any time the display controller spent fetching data from RAM was time the CPU or other chips couldn't access that same RAM. The less time the display controller spent on RAM access, the more time the RAM would be available for other purposes. If at a particular display resolution and RAM speed, a 16-bit bus would be 90% consumed by the graphics controller's display-data fetches, other chips would only be allowed to access the bus 10% of the time. Moving to a 32-bit bus would drop the display controller's overhead by half (to 45%), meaning other devices could access the bus 55% of the time. Even if the other chips could only perform 16-bit accesses, they'd still see a 5.5x speed improvement. Pushing the bus to 64 bits would cut the display controller's share in half again (to 22.5%), leaving 77.5% available for other stuff--another 40% improvement. Not as huge an improvement as going from 16 bits to 32 bits, but significant nonetheless.
Note that if one were using a higher color mode, it's possible that 16-bit bus utilization would have been over 100% (meaning a 16-bit bus simply couldn't handle such a mode), and 32-bit utilization might be over 50%. Under that sort of scenario, the improvements going from a 32-bit bus to a 64-bit bus would be more significant (again, even if no chips other than the display controller can exploit 64-bit accesses). Of course, if some other chips (e.g. ones that are designed for copying large chunks of display data) can exploit 64-bit accesses, those chips would receive even further benefit.
http://en.wikipedia.org/wiki/Nintendo_64#Central_processing_unit claims that the 64 bitness of the processor wasn't used that much, which makes me suspect that it was mostly a marketing effort.
The graphics co-processor may have had a SIMD-like behaviour (ie do 8 lots of 8 bit operations at once, or 4 16-bit operations), although I can't find a handy reference that confirms this. The nearest is this N64 manual, which says "At maximum speed (usually only attained with rectangles), two 32-bit pixels or four 16-bit pixels are written per cycle."
(The memory bus was apparently only 9 bits wide, which may have been a major limitation on polygon fill rate!)
From any practical point of view I can imagine it was mainly a marketing trick.
From today's point of view it is hard to even define what does "64bit CPU" mean. We can look at standard x86 family of CPU's. They are known as "32bit", although the latest models like Pentium 4 have got 36bit address bus and 128bit data bus. They contain several 128bit wide data registres, 128bit instructions, and can directly access 64 GB of memory.
The real main reason why we use x64 platform today is that Microsoft was too lazy to implement correctly the support for 36bit memory addressing into Windows XP. 64bit opearting systems eats a lot more memory, because you actually need to have both 32bit and 64bit versions of the system, also 64bit programs are bigger, because instructions are longer, all address are longer, etc. This means that a faster bus is needed.
Another point is that since their beginnings, gaming systems always used many special graphic acceleration chips so they were often successfully implemented with just an 8bit CPU without any significant degradation in quality of graphics etc.
If nothing else, copying portions of memory ought to go twice as fast on a 64-bit processor with a 64-bit bus than on a 32-bit processor with a 32-bit bus given similar clocks speeds. If implemented through a single opcode, this could be true regardless of what mode the processor is in. How much of this happened on a regular basis would probably depend on the game being played, though.