I'm interested in advancement mechanics that meet the following criteria:

* Self-balancing. System automatically compensates mechanical difficulty with adequate mechanical rewards.
* No empty tests. Every instance of resolution should count towards advancement in some way.
* (Optional) Ideally, various facets of the player's avatar advance independently based on their usage in play.

I'm specifically not interested in solutions of the following sort:

* Fixed rewards per session (see Exalted). Advancement should occur organically, reflecting stuff done.
* Experience budget (see D&D 4e or Beast Hunters). Stuff to do should not be subservient to prescribed rewards.
* Experience based on subjective judgment (e.g. role-playing awards or eyeballing the overal difficulty of the adventure), vague guidelines ("Every now and then give the player a dot here or there."), group vote or GM's whim.

Here's a few examples of advancement systems that more or less do what I need in princpile (even when the actual implementation doesn't work ideally in practice):

* D&D, it's kin, and the vast majority of crpgs award experience proportionally to the difficulty of the encounter (tougher monster = more points). Problems: xp values sometimes break (e.g. it's more difficult to defeat a single ogre than twenty goblins, but the latter yields more points); the composition of the party is typically not taken into account (e.g. it's considerably more difficult for a group of wizards to defeat monsters immune to magic, but it yields the same amount of points as for a group of warriors). This only works for combat, though. Various d20 games extend their Challenge Rating systems to non-combat encounters as well, but this tends to suffer from general inacurracy and empty tests.
* For my Street Fighter: The Storytelling Game retro-hack, I designed an experience system with rewards based on damage dealt, damage sustained and combat length. Seems to balance combat difficulty quite well so far, though with further playtesting it might as well prove open for abuse or turn out to favor certain builds. Not applicable outside combat.
* BRP grants the player a random chance to increase each skill successfully used during the session. Better skills have a lower advancement chance (but it's easier to earn experience checks for those in the first place). Problem: empty tests (after the first successful test in a session repeated skill use yields no additional rewards). The CoC variant I played also allows for training with time, which means that downtime effectively becomes an experience award based on GM's whim.
* In Burning Wheel the relative difficulty of tests is logged for each skill, based on a chart, and a specific amount of easy and difficult tests is required to advance that skill. Problem: extreme complexity; lots of empty tests (it's common for skills to be tested at difficulties outside the required range; only a single test is logged per extended conflict). Also, training skills with time leads to the downtime = experience issue.
* In Mouse Guard both passed and failed tests are logged for each skill, and a specific amount of both is required to advance that skill. Avoids the complexity of the above (no charts to consult). Balances mechanical difficulty very well, since every change in target number proportionally shifts advancement opportunities. Problem: empty tests (as above, though much less pronounced).
* In ORE every instance of resolution generates experience based on target number, I believe.
* In one of my games every test has a random chance to generate experience, relative to the probability of sustaining harm.
* DitV has Fallout. Problem: DitV is DitV.

What other methods to handle this exist?

I didn't notice the "checkboxes system," in any of the games you mentioned-though that may be a failing on my part.
I don't remember the game, but it worked something like this, you have 10 (or any appropriate number) boxes next to a skill, once you check all boxes, increase skill by one and erase all check marks.
I've only seen that with skills, but I guess you could have a counter for attacks (you would want 100 or so to increase I think).  With HP you could do something like "When you lose 10 times your HP, increase HP by 1 die" Which actually self-balances a bit since folks who get bad rolls will get more dice to increase their HP...
Not saying that is what you are looking for, but I wanted to make sure your list is complete.

edit:
By losing 10 times your HP, I meant keep track of all damage taken, when it reaches 10 times your HP, then you roll another die and add to HP.  Obviously someone who takes 10 times their HP without healing is very dead...

Seems like you could turn the DC of any action into XP for the skill used to accomplish that action. The number you have for that skill x10 would be the xp needed to level it. Failing a skill adds a flat rate like +1xp or +3xp or some such, so a character that kept at it with a skill would eventually learn how to do what ever they are attempting.
I think this way would let characters with low skill ranks learn rather quickly to get them in the middle skill ranks, but getting into the higher skill ranks would require either alot of time for training, or constantly tackling very complex and challenging tasks.
Would be a considerable amount of book keeping though.

Rune has it's own approach.

Encounters etc. are designed from a budget, which does the balancing.  In designing an encounter, the runner (GM) specifies which skills etc are relevant to the encounter.  If a character succeeds with one of the listed abilities in that encounter, they put a mark next to it on their charsheet.  After the encounter is resolved, the player may spend victory points (earned by overcoming encounters) on one of their marked abilities to raise it by 1 rank.

I use the checkbox system in Night and Day, and it works wonders. Basically, every time you fail at a skill roll (including combat skills), you fill in a checkbox for the cost of 1 XP. When you have checkboxes equal to twice your current skill rating, you upgrade your skill without any additional experience expenditure. It's a very solid system that makes characters advance based on what they have difficulty with, learning from their mistakes, and so forth.

You could modify RuneQuest's mechanic.

Each skill gets a check the first time it is used successfully each week.  (You would put a check box for every successful use to avoid "empty tests".)  At the end of the week all skills with checks can go up a small amount if percentile dice roll over the skill.  (You would give this chance for increase a bonus if more check boxes.)  So by experience, low skills increase regularly.

Furthermore, acquiring training (with a book, teacher, etc.) allows a certain increase at the end of each week.  The amount if increase is different from the increase by untrained experience--at least slightly more, possibly dependent upon the value of the training.

why do you want advancement like this?
is it more realistic?  does it encourage the player to act in a certain way?

in fiction characters rarely improve.  Luke improves a lot in Star Wars, no one else does.  Indiana Jones never improves - he was great at the start and stays that way throughout.

in games players want their characters to improve as a form of reward.  They don't necessarily want it to be realistic.  If you want it to be realistic that's fine - but remember that realistically characters will spend their time reading books for knowledge, at the firing range for gun skills, etc.  They don't go into real combat to get better with combat skills.

I like the idea in theory of getting advances when you fail at something - it means that at a certain level you won't advance much.  So there is a natural limit to improvement.  But that gets to the practice issue.  If I learn swimming by failing at it, I'm going to spend my time in a pool practicing.  I certainly don't want to try swimming for the first time when my life depends on it. 

So I would avoid making a game based on realism and then not expect players to behave in a realist but very boring manner.