Plenty of oldskool Japanese RPGs were quite nonlinear in the way western RPGs are...
FF1 - fairly linear (though still a large world map to explore) in the outset, but after creating the canal, you could take on the Fiends in any order.
FF2 - you could theoretically travel from one point of the world map to the other, without ever setting foot in the second town. Of course, the monsters would probably make mincemeat out of you way before then, but hey it's still possible.
FF6 - World of Ruin, of course
Phantasy Star 1 - once you get the Spaceship, you could go wherever you like... several dungeons (to get the best weapons) are completely optional, but you needed to get the Eclipse Torch to get the Laerma Nut, and the vase to store the nut in... so Myau could transform atop the tower of Baya Malay. REALLY difficult game to figure out without a walkthrough.
DQ1 - mostly just grinding and collecting 3 items (Erdrick's Token, Rain Staff, Sun Stone) to get to the final boss tower.
DQ3 - collect 6 orbs to revive the great bird Ramia, could do this in any order you want.
Romancing SaGa/SaGa Frontier - extremely nonlinear, plenty of characters
FF10 was really the first game that was like a point A to point B uber linear experience, and it was one of the main things I disliked about the game (the other being distinguished mentally-challenged minigames). I don't really have high hopes for 13, especially after the Japanese reviews.