I don't think whether a choice is meaningful has much to do with whether it's an RPG. Plenty of non-RPG games have meaningful choices. And
good game will have meaningful choices.
But I think an RPG is derived from choices that
effect your character, choices about how you are going to play your role.
Linear RPGs like Final Fantasy are definitely RPGs, even though the story is linear, because the choices you DO make, as simple as most of them are, are all about defining your character.
If two hallways lead to the same place, but one hallway has a dodging reactions challenge and the other has an underwater swimming challenge, picking one or the other is a meaningful choice, but I don't think it's a choice that is symbolic of an RPG.
If two hallways lead to a different place, but your character remains the same regardless of his choice, I don't think that is symbolic of an RPG either.
If two hallways have the same challenges and lead to the same place, but one gives you an a bonus to magic damage at the end and one a bonus to physical damage, THEN I think we're getting somewhere - even if they are otherwise identical, that you have made a conscious decision on how to change your character, I think you've got RPG elements.
If two hallways are the same and go to the same place except for who you bring with you, and later in the game your character remembers that and has an additional dialogue choice with that character, I think that's an RPG thing too.
Let's take your example:
Consider a game where there's a prison atop a mountain, run by religious zealots. You can try to sweet talk your way in, or disguise yourself as a zealot, or sneak in through the haunted caves, or just plain attack the place - which is very difficult. But that's a strategy choice. Why are you even going in there? Oh, right, you need to rescue Jimbob who knows where the Heart of the Mountain is hidden. A good RPG would include other ways to get that information, so you can decide that rescuing Jimbob is just not what you want to do.
I think, even if you have all of these options - if, in the end, there is no change to your actual character, if he's still the same when you've finished, I don't think this is an RPG. If there's only a change in the world, but no
personal and conscious progression, I think you've certainly made a situation with interesting and meaningful choices with consequences, which is great, but you haven't made it any more rpg-life.
I should add, however, that it really only needs to change the character in the eyes of the player - it doesn't have to be mechanical. Bringing it back to Walking Dead, ultimately a lot of your decisions aren't really "meaningful" - you can't change the world, or what happens, to any great extent. The only thing you can change, and this, I think,
matters, is who you are. Your role is strongly fixed, as is the story you are taking part in, but every choice you make influences who the person you are playing
really is.
If you decide to crush a man's head or try to resuscitate him, it may not end up mattering insofar as it's impact on the world - but it's written into your character's history, now. You are now the sort of person that does one or the other. You come out a different person - even if the rest of the world stays the same, you have changed.