The best way to indicate progression is visually. Fable actually nailed this early. But I think the idea should expand across all RPGs the FF system of constant untouched beauty throughout an epic adventure (just silly) is a carry over from their NES days and frankly, its dumb. A really important aspect of this should exist in battles, these visual cues could be reminders of old battles, where the player's play style is represented visually. Even the original Doom had a visual representation of the character's status, why not now?

Monster's could recognize these aspects as well basing their choice on how to engage the player character's on the visual elements that define their skill and might.

I'm thinking for something similar, but i'm working on a browser game, so it's not like i have to put much graphic to make it look cooler.
I recently thought about the "character behavior" of the hero controlled by the user.

Example: There are 5 stats: strenght(aggressive), dexterity(elusive), constitution(defensive), intelligence(frenetic) and charisma(supportive), when you add a stats point to strenght it give +1 damage with meele weapon, +4 carry weight and +0.2% aggressive; when you add a stats point to dexterity it give +1 damage with ranged weapon, +1 dodge and +0.2% elusive.
Basically we have stats and behavior, when you add stats u get a "bonus" to behaviour, when u do something connected to that kind of behaviour, u get a bonus on that behaviour.

The enemy of course reacts differently to different heroes that have different behaviour. Someone that is a lot aggressive have more chance to scare a frenetic enemy, at the same time an aggressive enemy have more chance to scare a frenetic hero instead of a defensive hero (constitution).
So if you connect these two mechanisms you can get a little more complicated combat that isn't related to elements(fire,water,etc) and is role-playable(?).

What do you think?
Of course if u are working with 2d or 3d u can, as suggested by Mratthew, make this work with the look of the hero too, and that would be cool .

Alterations to appearance from stuff that happens in games makes some sense. Personally, I like the whole cause and effect thing to be obvious. Your character gets stronger so you get bigger muscles. You get injured so you start to show scars. You dabble in mystical arts so maybe you have an aura about you or some other physical characteristics. I think Fable had all of these. But a change in appearance just because you're being sneaky doesn't make sense to me. Not unless it's maybe tied to your gear. If you're trying to be sneaky all the time you're trying to blend in so why would your character's appearance stand out?

Guard: "Look out everyone, a thief is approaching. I can tell by his dark hood."

On another thought, there could maybe be quests where the player wants to somehow counter or conceal the automatic appearance changes without loosing the attributes gained.

It binds your artistic vision to the player's choices. Say a player levels up their unarmed combat skill. Do you make them look like a Shaolin monk, or like a boxer? Maybe my vision for my character is that of a lithe, disciplined warrior, and pursuing that makes me into a musclebound goon. Maybe I want to be taller, but don't want to take up archery to get there. Every time something I do makes my guy look different, it'll be like you're judging me. "Oh, I see you use stealth to avoid confrontation. Now you look like a craven rodent, because that's exactly what you are."

The player should differently have a choice in this. You don't want the player to have to change his actions to change his looks. How about something where the player can choose to revert to a previous look, such as how a thief-turned paladin might be able to infiltrate the thief's lair.

Visually some of the most dramatic changes a character should show off is skills in my opinion. When a character first picks up a sword they will hold it awkwardly and swing it clumsily but this doesn't last. As long as a character survives they will learn and master what they focus on. This is the sort of thing that I'd like to be apparent on character progression.