OK, so, to begin: you are going to get +2 Dexterity, which is nice-ish, −2 Constitution, which sucks but at least you’ll get bonuses and d12 HD, and you will get a bunch of other stuff that barely matters at all. For reasons, you probably will not be using any traditional elven weapons (though the less traditional elven-specific weapons in Races of the Wild are solid options in a couple of cases). Thus, your elven race would be a moderately-large downside, a sort of mediocre ability score bonus, and not much else.

The solution to this is taking advantage of various elf-only options. That means you are going to need Races of the Wild, since that’s where most of them are, and Tome of Battle, because there’s two excellent things in there for you.

There are three primary prestige classes I have in mind: champion of Corellon Larethian, eternal blade, and wildrunner. They do not all work together, sadly, at least not completely, but we can still work with this.

• Champion of Corellon Larethian—more knightly/paladin-y than you’re looking for, but two levels do allow you to add your Dexterity bonus to damage with certain weapons. That’s very valuable. Unfortunately, requires a stupid number of feats, too many to make workable, and the elegant strikes feature (read: the reason we care about the class at all) is incompatible with Shadow Blade (which does the same thing for a different set of weapons, and for fewer and better feats) unless you get a favorable ruling about elven lightblades and Shadow Blade.

• Eternal Blade—this thing just oozes cool—it’s basically Link, Hero of Time. Furthermore, the capstone is extremely useful: once per fight, take two full-attacks in a row. You will be a crazy frenzy of blades.

• Wildrunner—this is the big one, the crazy elven barbarian. It gains a “primal scream” class feature, which works very similar to rage, and stacks with that. Notably, it has a big +6 bonus to Dexterity.

Feats

Your first feat has to be Weapon Finesse. You have a bonus to Dexterity, this build relies on Dexterity, and you have to be able to hit things. What this means is, unless you have Flaws from Unearthed Arcana, you will not be able to get the Two-Weapon Fighting feat until later. Even with them, because of the feats you need to get that are not fighter-bonus-feats, with flaws I still recommend delaying Two-Weapon Fighting in order to ensure other feats on time.

If you do not have Two-Weapon Fighting, you should not attempt to use the two-weapon fighting combat option. Sorry, but you only get one feat, you are going to have to be Dex-focused, and without Weapon Finesse a Dex-focused melee fighter isn’t going to hit anything.

After Weapon Finesse and Two-Weapon Fighting, the next priority is Shadow Blade, from Tome of Battle. This allows you to add your Dexterity bonus to damage when using one of a selection of weapons—the short sword is the one for you. The issue is getting a Shadow Hand stance to use it with. This either means Martial Study and Martial Stance before you can get it, or taking a level in swordsage. The problem with the latter is it will slow down entry into eternal blade, and make its capstone impossible pre-epic.

Extra Rage from Complete Warrior is a good idea; barbarian itself gives more uses of rage only slowly.

Improved Two-Weapon Fighting can be gotten from the gloves of the balanced hand item from Magic Item Compendium. The same book has rules for adding enhancement bonuses to Dexterity to this same item without a cost penalty; obviously, Dexterity is your most important score. This build is very feat-starved, so the item makes more sense than picking up another feat. You can always pick the feat up later to replace the item.

It’s not a feat, but Twisted Charge from Complete Scoundrel will do you well.

Items

Shadow Blade only works with a select group of weapons, and you require Weapon Focus for eternal blade, so it makes the most sense to use paired short swords: they’re the best items available for dual-wielding that work with Shadow Blade. Before you get those feats, though, any combination of weapons you want to use works.

Note that Expedition to Castle Ravenloft has a sun sword, a +1 short sword that deals the damage of a bastard sword. It’s basically the sun blade without all the extra crap you don’t need; instead it costs 3,000 gp. As in, not quite 700 gp more than a +1 short sword usually would. This makes an excellent weapon to build off of; that d10 represents a +3 damage bonus over a short sword, on average. The sun blade itself is saddled with too many weak enhancements and just costs way too much money. Make sure your DM agrees that the sun sword works with Shadow Blade, too.

This doesn’t work for the OP, since he cannot use Dragon material, but for other readers: If you cannot get the sun sword or it doesn’t work with Shadow Blade, you might also consider elven lightblades, which are kind of like combo short sword/rapiers. Again, check with your DM that they are short sword enough for Shadow Blade; strict RAW, they’re not. These are exotic weapons not even remotely worth the feat you’d normally need to use them, but you’re taking a couple of levels of fighter anyway for feats, and the exoticist fighter variant from Dragon vol. 310 can get you proficiency effectively for free. Note that elven lightblades are the only possible way to have one weapon get bonuses from both elegant strikes and Shadow Blade; see the “Champion” build below for that.

Otherwise, just use short swords. The actual weapon you use is really not that important as long as it is light and works for Shadow Blade.

The gloves of the balanced hand have already been mentioned; making them double as gloves of dexterity is also an obvious priority. Also, you still do add half your Strength to damage, and your HP is on the low end, so a belt of giant strength and periapt of vitality are worthwhile, albeit at a lower priority than Dexterity. Get the best cloak of resistance generally available. Magic armor, probably angling for the fortitude or soulfire line of special abilities, is obvious. Mithral is probably your special material of choice, considering your high Dexterity.

You are going to want a speed weapon if you cannot get haste reliably cast on you. With your Dexterity, it may be difficult for your wizard to even have time to cast it before you go, and you want it for your first turn. The collision property is nice in that it multiplies on a critical hit, and various energy damage properties aren’t awful. But don’t ignore utility on your weapons; eager and warning are excellent about letting you go first, and there are weapons that improve rage or what have you, and so on. There are a lot of guides about which weapon properties you should use; this build does not have any special needs here.

Aside from that, keep up with your list of necessary magic items and peruse Bunko’s Bargain Basement for spending the rest of your money. This build does not include any built-in flight; if your alignment is flexible but your game is enforcing alignment-based rules, it’s worth being Evil just to have access to the feathered wings graft.

Barbarian 1

Your first level, your iconic level. You get rage and fast movement. You should be trading away both of these.

Rage Variant

For rage, your options are either ferocity (gain bonuses to Strength and Dexterity rather than Strength and Constitution, activate as an immediate action) or whirling frenzy (gain an extra attack). I like whirling frenzy better, but both are very solid options. Whirling frenzy will allow you to “pretend” two-weapon fighting without the feat, though.

Spiritual Totem—Lion

Complete Champion has a series of alternate class features to trade away Fast Movement for something else based on a spiritual totem. The Lion option is pounce. You need this. This is the difference from a mediocre damage build with no mobility, and a mobile damage build that is hard to pin down.

Barbarian 1/Fighter 1

Stepping aside into fighter, because you need feats. If you don’t have flaws, this is where you get Two-Weapon Fighting.

Hit-and-Run Tactics

You also take the hit-and-run tactics variant from Drow of the Underdark—you don’t need to be drow, and it allows you to add your Dexterity to damage rolls when made against flat-footed targets. That’s pretty cool, and it only costs the armor and shield proficiencies you wouldn’t use anyway. And you get +2 to Initiative, to boot.

Exoticist

This variant from Dragon vol. 310 isn’t available to the OP, but for others it may be useful. It gets you four exotic weapon proficiencies instead of all martial weapon proficiencies. You already have the latter from barbarian, so that’s no loss, and elven lightblades arguably function as short swords for the purpose of Shadow Blade. It’s a small bonus, but it’s basically free. And if you do manage to get into champion of Corellon Larethian, it works with elegant strikes, and thus the benefit is no longer anything like “small.”

Pugilist

This variant, also from Dragon vol. 310, focuses on unarmed strikes, which you won’t use much (though you could, since they are Shadow Hand weapons), but it importantly grants Improved Unarmed Strike and Endurance as free bonus feats, on top of your usual 1st-level bonus feat. It conflicts with hit-and-run tactics, and it doesn’t offer the opportunity to use elven lightblades (at least, not for free), but you need Endurance for wildrunner, so that is a pretty big deal.

Barbarian 2/Fighter 1

Uncanny dodge is nice enough. Not much to say here, class-wise.

However, it is 3rd level. Time to pick up Endurance, to qualify for wildrunner on time. Unless you went with pugilist, in which case you can actually accelerate some of your other feats. This option is best if you don’t think you’ll finish up your feats.

Barbarian 2/Fighter 2

Back to fighter, because you need feats that badly. Trap Sense is near-worthless; though Flaws can eliminate the need for fighter here, I still don’t recommend barbarian.

The feat you need here is Martial Study for a Shadow Hand maneuver. This allows you to get Hide in-class (which you’ll need for wildrunner), and you need a Shadow Hand manuever for Shadow Blade. Your options are shadow blade technique, which could easily be refluffed as a two-weapon technique, and clinging shadow strike, which gives the target a 20% chance to miss for the round after you hit.

Alternatively: Barbarian 1/Fighter 1/Ranger 2

Skills are a problem; wildrunner requires a ton of them, and barbarian and fighter are not high-skill classes. You can do well with half-decent Intelligence (eternal blade gives you a few bonuses based on it), but it’s worth noting that we’re getting Two-Weapon Fighting and Endurance—bonus feat options for Ranger 2 and 3. Thus, you can replace two levels of fighter with those two levels of ranger, which is a high-skill class (the elf substitution level in Races of the Wild even give you 8+Int!). The obvious problem is you can’t just jump to Ranger 2, so you also lose a level of barbarian as well.

We also really do want a level of fighter for hit-and-run tactics, lightblades, and/or Endurance, so trading one level of fighter rather than both, and only going to Ranger 2, is advantageous. That probably ends up being the best choice: you lose out on uncanny dodge, and an average of 3 HP (4 HP if you do take the elf substitution level, since it has d6 HD), but you retain hit-and-run tactics.

Ultimately, this works out to a lot more skills, better saves, a favored enemy, and Track and wild empathy, at the aforementioned cost of uncanny dodge, and 3 HP.

Barbarian 2/Fighter 2/Crusader 1

You gain five manuevers, a stance, and the ability to delay a small amount of damage you take for a round, gaining bonuses when you do so. Very barbarian-esque. Two of the maneuvers (or one maneuver, and the stance) need to be Devoted Spirit for eternal blade. Note that, since you’ll want to use a Shadow Hand stance in order to use Shadow Blade, your choice of stance matters only until you get that feat (which sadly won’t be for a while unless you went with pugilist).

Note that, if you like any of the 1st- or 2nd-level Stone Dragon maneuvers, now is the time to pick them up; Eternal Blade doesn’t get the discipline as an option. So definitely get mountain hammer (though its out-of-combat utility means that would be my recommendation anyway), and any others you like.

Battle leader’s charge gets a fairly sizable damage bonus (+10) on “your charge attack.” Ask your DM how pounce interacts with this; it’s completely unclear. If you cannot benefit from pounce while initiating battle leader’s charge, it’s not worth it; your other attacks should add more than 10 damage. If you can get pounce, and the +10 applies to all of those attacks, your DM is insane and this is by-far the most powerful thing you could grab right now. If I were your DM, I’d give you the +10 on the first attack, and let you have the rest as normal. Note that battle leader’s charge requires that you have some other White Raven maneuver or stance to take it.

Beyond that, I like tactical strike for a decent damage bonus if you can’t full-attack or charge, plus it lets your allies reposition, which is nice. Crusader’s strike is solid enough if you need emergency healing.

Alternatively: Barbarian 2/Fighter 2/Warblade 1

(or Barbarian 1/Fighter 1/Ranger 2/Warblade 1)

The thing about eternal blade is that it requires maneuvers from Devoted Spirit or Diamond Mind, but then learns maneuvers from Devoted Spirit, Diamond Mind, Iron Heart, or White Raven. That weird mismatch makes it very annoying for you to qualify as a warblade: that class doesn’t get Devoted Spirit, and Diamond Mind uses the Concentration skill heavily—which you can’t use while raging. You could take stance of clarity and emerald razor, which are the only two Diamond Mind maneuvers at this level that have nothing to do with Concentration. Those maneuvers aren’t bad, but probably wouldn’t be top picks for you—and to make matters worse, a 1st-level warblade only gets 3 maneuvers and 1 stance, so you only get 2 more maneuvers after those.

However, you might consider asking your DM if you could use Iron Heart and/or White Raven maneuvers to qualify for eternal blade. If you can, warblade becomes a much more serious contender: you still have access to battle leader’s charge and mountain hammer, and can also take an Iron Heart maneuver like punishing stance or wall of blades. Those are strong maneuvers (and punishing stance is very on-theme, though sadly you’ll have to ditch it for a Shadow Hand stance pretty soon for the sake of Shadow Blade), and perhaps more importantly, having an Iron Heart maneuver makes it much easier to learn appropriate-level maneuvers later when you take eternal blade.

Barbarian 2/Fighter 2/Crusader 1/Wildrunner 5

First level of wildrunner is lackluster, but you’re in! Congratulations, that’s awesome. From there, we just keep taking levels. None of the class features present options, but the primal scream feature is the big one to look for, especially the initial 2nd-level version. Hide in plain sight certainly isn’t terrible.

Your sixth-level and ninth-level feats need to be Weapon Focus (short sword is your best bet) and Martial Stance for something Shadow Hand, respectively. If you wait until 9th level, you can take assassin’s stance for +2d6 Sneak Attack damage, but the 1st-level child of shadows and thicket of blades options are both quite good as well. For that matter, the other 3rd-level stance, dance of the spider, is pretty damn cool.

Note that if your DM allows some houserules that make it possible to get into champion of Corellon Larethian, trading two levels of wildrunner for two levels of that is very much worth it.

Barbarian 2/Fighter 2/Crusader 1/Wildrunner 5/Eternal Blade 10

At eleventh level, start taking eternal blade levels instead of wildrunner levels; you have the best things from wildrunner, and eternal blade is an awesome prestige class. I suggest focusing on either Iron Heart or Devoted Spirit maneuvers, but feel free to take whatever looks cool; it will be. Avoid Diamond Mind, as it is incompatible with rage.

The feats you have left to get are Shadow Blade (finally) and Extra Rage (finally). Both of these may have been gotten much earlier if you have Flaws.

Final Build

1. _{The exoticist variant fighter requires Dragon content and is unavailable to the querent. In that case, regular fighter is fine, elven lightblades don’t really add that much anyway. If you can get a pair of sun swords, you may not even want them.}

Final Build with Flaws

Flaws dramatically improve things by allowing you to take Shadow Blade and Extra Rage much sooner.

1. _{The exoticist variant fighter requires Dragon content and is unavailable to the querent. In that case, regular fighter is fine, elven lightblades don’t really add that much anyway. If you can get a pair of sun swords, you may not even want them.}

“Starting high” Champion build with Flaws

This build has two conditions before I’d consider it:

• The game is starting at a minimum of 10th level.
• The DM allows the elven lightblade to not just count as a short sword for the listed feats, but also for Shadow Blade.

It also relies on Dragon, which the OP explicitly cannot use.

Anyway, the idea is to use an elven lightblade rather than a short sword (or sun sword), and thus get Dex-to-damage from both Shadow Blade, and the champion of Correlon Larethian’s elegant strikes feature. That’s a pretty big deal, a much bigger deal that the sun sword’s bastard sword damage (+3 vs. something in the 15-17 range at 20th).

Qualifying for champion of Corellon Larethian remains inherently problematic, though. I’d very strongly consider whether or not I could do more with three feats than elegant strikes does. I probably could, particularly since this build can’t get hit-n-run tactics. Dodge, Combat Expertise, and Mounted Combat are not good feats. Combat Expertise doesn’t even work while using rage.

Fighter does help a lot here, though; the exoticist variant from Dragon vol. 310 gets Exotic Weapon Proficiency four times. This is important because we want to use an elven lightblade, but we also need proficiency in elven thinblades or courtblades for champion of Corellon Larethian.¹ Which you choose, and what you do with the other two proficiencies, doesn’t much matter since this build relies heavily on those elven lightblades. A braid blade (Dungeon vol. 120) is probably the best choice just because it’s another free attack, though it won’t benefit from Shadow Blade or elegant strikes.

We can also add back that second level of fighter (or third level of ranger, if ignoring multiclass penalties; I tend to feel 4 skill points is well-worth an average 1 HP) to get another feat, since Wildrunner 3 isn’t exactly an amazing level.

Note that warblade is no longer an option; we need crusader for heavy armor proficiency. We have to skip hit-n-run tactics for the same reason: it prevents us from gaining heavy armor proficiency from multiclassing, we would have to actually take Heavy Armor Proficiency as a feat and we can’t afford to. Not that we would be caught dead in heavy armor (or equivalently, being caught in heavy armor would be a death sentence), but champion requires it so have it we must.

You can also delay Martial Stance until 9th, for the option of taking assassin’s stance, which opens up Craven (Champions of Ruin) for a large damage boost when you attack opponents in a sneak attack situation. Attacking with elegant strikes, Shadow Blade, assassin’s stance, and Craven is looking at +60 damage per attack (while dual-wielding high-crit weapons and only 2d6 of that damage doesn’t get multiplied on a crit).

By the way, in case that last line didn’t suggest it, a pair of scabbards of keen edge are good high-level investments. Improved Critical is fairly-obviously not a great choice, seeing how feat-starved we are, and keen is more expensive in the long run (keen is cheaper on a +4-equivalent weapon, but more expensive on a +5-equivalent or higher).

In general, crit-fishing is a fairly low-power strategy, but we have several things going for us here. We are already maximizing our attacks per round (TWF, pounce, whirling frenzy, speed or haste, island in time), we are already using high-crit weapons, and we already have a ton of unrolled (read: crit-multiplied) damage. When 16k becomes cheap at high levels, doubling our already-solid chances of getting a crit that’s going to hit ridiculously hard without us doing anything extra for chump change is a no-brainer.

1. _{Weapon Focus (longsword) is another option, and it would pull double-duty qualifying for eternal blade, but we don’t use longswords, and getting the proficiency free gives us more latitude in when to pick up that Weapon Focus feat.}

Let them die or be a hero despite their flaws. Those who live by the [dice] die by the [dice].

By rolling characters, and choosing not to build for combat prowess, you clearly have a very specific and challenging game in mind. While I would recommend investigation into other systems that may better fit your needs; the situation you've set up here has a very traditional solution: the character attempts to do the quite difficult, as built into his/her narrative arc. The character will either succeed or fail on their own merits, making the story that much sweeter or bittersweet, as appropriate.

In the gaming tradition, characters were played as long as they lasted. Let the arc play out for this character, as his/her choices dictate. Any changes to the character would by definition be optimising, as you're now trying to accomplish a specific mechanical goal (likely combat prowess.)

To avoid optimising, tone down the monsters you throw at the party, to suit their skill and the narrative requirements. Alternatively, the player can look at Anger Management, the pathfinder handbook for barbarians, and on their next level up (assuming they survive so long) make a more informed (nay... optimised) choice as suggested by the options presented in the handbook. I choose to build to requirements because random chance has not been merciful to my prior characters (to avoid a rather more vulgar hardware related phrase.) A quick review of the document suggests that the addition of a mount can do quite a lot to compensate for the halfling's ... diminished capabilities. Provide an opportunity to quest¹ for a Giant Gecko mount and a quiet retcon to the mounted fury archetype.