Sorry, I was wrong!
I just looked it up. The differential swap is possible. It is not cut into the shaft (5th gear is however making that a custom job).
Good write up on a Toyota trans rebuild:
C52 transmission rebuild
Sadly, I don't think you'll gain a ton of ground there. The lowest final drive I know of is a 3.722 for a C series transmission which I am assuming you have (not totally sure). That will only drop your rpms by about 160 @ 100 kph. The only thing lower is what they've been putting in the diesel transmissions. I don't know what is available for you in Australia, but if you could find a C series trans out of diesel you'd be much better off just swapping that whole thing onto your bellhousing.