Since you're looking at Final Fantasy anyway, let's talk about Materia! ^_^ The materia system used in FF7 arguably fits into neither of your categories, because the player chooses which ability trees to evolve but cannot lock themselves out of branches. (Well, I guess you could miss a unique materia at an area you can't go back to or never find in the first place, but you could compensate for that by making all materia available through some kind of prize system or shop near the end of the game, or by a gazette system such as in Vagrant Story which lets a player check whether they have obtained all treasure in an area before leaving.) It's entirely possible for a player to master at least one of every materia before ending the game, and the process of combining mastered materia into huge materia allows you to equip the majority of that skillset onto one character if you want to. The materia system has one major downside - the fact that specific materia are difficult to tie to the development of specific characters or the story as a whole. In FFCC the materia system is slightly different - instead of experience going onto whichever materia are equipped, it goes into a pool which is your main crafting resource, the energy used to combine loot (both low level materia and items) into higher level materia. Perhaps more importantly, the fact the FFCC has only one playable character reduces the problem of tying materia development to character development - all materia are the playable character's personal materia, and all are obtained as gifts to him, by his combat efforts, and/or by his shopping with his money.

Now for something completely different, let's look at Vagrant Story and BoF Dragon Quarter. Both of these are games where the skills you learn and the order you learn them in are more or less linear, but they are also both New Game Plus games, where the player is expected to complete the game at least twice to unlock all areas and learn all skills. I don't think that either Vagrant Story or Dragon Quarter has any new skills in the areas unlocked after the first playthrough, sadly - that would have been interesting. But the main point is that, for both of these games, the game may control when you first get each skill but the player has a lot of control over leveling up the skills. In Dragon Quarter you level up skills by using them and their effectiveness as well as your capacity to use them multiple times are both affected by the gear you equip. There is also one area where you can choose which boss to fight, and each gives a different skill as a reward. I didn't actually like the way this was done - they should have either done it several times throughout the game, so there were several new skills to get on the second play through, or given the player a way to repeat that area within a playthrough to get a second skill, or something. In Vagrant Story some skills are unlocked as a drop from monsters after you get the first level of that skill in the predetermined, plot-related way; gaining a second copy of a skill, whether as a drop or by going through the game a second time, levels up that skill (excluding the puzzle-related skills which don't have higher level versions). Vagrant Story also has a single playable character like FFCC, so again it's a situation where one character is supposed to learn everything by the end of the game. Dragon Quarter instead locks skills and some gear to each character, and controls who is in your party at any time, which gets a bit frustrating on the 2nd play through.

Also, about random battles to raise stats, Final Fantasy 8 had monster difficulty be relative to the player, so FF8 did not really allow the player to grind for stats. There are also many RPGs, from ChronoTrigger to Zelda: Twilight Princess to Skyrim, which have a much smaller % of random battles and a much higher percentage of placed opponents that stay dead once the player kills them off, unless the player leaves the area.

Not sure if this is like the materia (haven't played FF7/FFCC), but there are many games that make it so that equipping collectible items lead to you getting certain abilities and combining them strategically in available slots can lead to unlocking new abilities, so there is experimental/discovery stuff going on that adds to the enjoyment of the game. Could also make it so that those items themselves can level up and "evolve" into new abilities.

Then you have things like Transistor where you have a single "skill" that can be equipped in 3 different slots as either an active ability, a modifier to an active ability, or a static ability. (excellent game)

Also, as for the web and tree systems you mentioned, the web isn't necessarily "arbitrary choice and luck" since, if you want the player to feel more directed, you as a designer are completely free to sub-develop these webs into smaller webs, highlight paths, or create 'organic' combos that the player will immediately see and think, "oh I should go this way for this kind of character!" that in turn leads them towards the abilities they need for that sort of character.

As for just leveling up the player linearly, the degree to which it feels like a "grind" is entirely the system designer's fault (as you described). If the gameplay experience-gain rate is slated low, then the player will have to grind. On the other hand, if you give the player the opportunity to get lots of experience more easily or if you balance the game by default so that the player has the right amount of experience by the time a skill is unlockable or needed, then the player won't feel the "grind" because they won't be battling JUST to get experience, but rather they'll be battling as they progress and happening to develop at a reasonable rate along the way.

Notice, however, that the balancing needed for the experience gathering rate will be the same all around so long as you have a leveling system. Levels and experience automatically result in a need for number-crunching, regardless of whether you want to do that or not. Easiest route in that case is to have a fixed number of battles, but if you REALLY wanna have random encounters, then yeah, you need to figure out exactly how many of those random encounters you will expect a player to go through before they are prepared for the next challenge area. Other alternatives are games that do NOT have a leveling system and instead rely solely on players developing skills naturally and unlocking new abilities by completing game objectives directly and/or finding items ala Legend of Zelda / Dark Souls.