Q: Is a No Battle/Encounter Hack possible?

I have to agree with Tenkarider, the whole idea would be very, very, boring. Why? Beyond the obvious reasons, most of the dungeon crawling or long walks to the next town would put you to sleep. If you wanted to speed up the process, without making it completely mind numbing, just decreasing random encounters would be a better idea than removing them. Just as Tenkarider said except with the charm bangle effect.
But, if you really wanted to just to view the game (although you really wouldn't be seeing much but thats personal opinion) and you wanted to do it with minimal hacking skill:
Find an IPS patch for general bug fixes,
Open up FF3usME, raise all characters begining levels, stats, magic, etc to max (Basically just cheat your ... off)
Again, in FF3usME, set the No rand. en. effect to pretty much every item. Add super uber items to all character's starting equip etc. (again, cheat your ... off)
At this point, there would be no random battles, only scripted story stuff and you'd so unkillable they'd just feel like any other event.
The only issue that would come up at this point is, as Abyssonym said, recruiting Gau to progress the story, then in the WoR recruiting Gau and Gogo. (Gau random encounter on Veldt and Gogo requires random encounter getting swallowed). With some minor hacking that would be fixed to. Gogo, just find his normal place in the cave and drop him in a town with the same script/dialog for recruiting. Gau, still pretty simple but some work, do the same thing and make a recruit script.
Moral of the story? Most of what your asking for can already very simply be done with standard cheats. I don't really see anybody spending time on actually doing it as a hack. Just my two cents though for what its worth.