Grek, if you don't mind, I'd like an exact reason as to what is wrong with the Awakened Cat.
It's not core, but it's all freely available stuff.
Awaken SpellCatAbility adjustments gotten from subtracting 10 or 11 from the SRD figures.
Next I compared it to other similar monsters turned into PCs, and dropped the Hit Dice added to it in exchange for Cleric Levels. This might be where the problem is? With 3 being the max level, and ECL being Hit dice plus Level Adjustment plus any class levels, that would make it a cat without any use to the party at all for another level. While establishing the RP would be fun for a few sessions, it could easily tick players off. Something tells me this wasn't where the problem was though.
Anyway, On to understanding your information here...
The Holy Alfheim Empire is not at war with anyone, but hates the Elfin Kingdoms because the Elfin Kingdoms supposedly betrayed Merica.
This "betrayal" was The Elfin Kingdoms' desire to avoid further conflict with The Aboleth States, whom had previously conquered a member-kingdom of the Elfin Kingdoms in the last confrontation 20 years ago. This was a violation of Treaty obligations they had with Merica.
Merica had been fighting the Aboleth states for some time over the ownership of some prime location reefs, and the Empire feels that the Elfin Kingdoms failure to meet that obligation was responsible for the Aboleth advance that has pretty much split Merica in half.
Did I get that all right?
If so, why does the Empire care about Merica? I didn't see that at all. Ostgard is in between Merica and the Empire, and Ostgard isn't even a vassal state yet. It also has a race that for whatever reason felt it was a good idea to get the hell out of the Empire, hinting at genocide from the empire. This makes me think there would be bad blood between them, which would make me even more curious as to why the Empire cares about Merica at all? Is it just "We know we'll be next", or is there some kind of link between the two groups? Also, how many years exactly did the Galland war happen? Grand Nephew implies to me somewhere around 40 years or more.
Unterhold seems to be bitter about it's relationships with the Empire and Gnomheim. It seems like they want to break their ties with the Empire for whatever reason, but don't dare because of their war with the Aboleth states. I'm thinking there is something in the empire's angelic nature that is dangerous to the unlife of the Unterhold counts. This makes them want to get some separation, and the Proselytizing by the Empire priests makes for some bad blood.
Did I get this right?
Okay, so, contingent on being correct, and that you continue to refuse Mister Puffins (Whom I really, really like), here's my thoughts on another possible character.
A Troll Samurai from Dramscrag. The problem with this one is that it's a +5 LA. Therefore this character cannot easily be done, and will require doing monster advancement as covered in Savage Species. This would be something that I could play. I imagine it could be some trollish variant that isn't as strong as a full troll, but being a troll would be critical to the RP as I see it.
His lord felt dishonored when they were ordered to hold back from the war. He sends some of his Samauri on quests to find ways to help the Merica without violating his own oaths to the Elfin kingdoms. One of the ways is in assisting the Empire explore the sea, since the empire is not Merica and the empire is saying it's exploring the Sunless sea so as to find things that might help against the Aboleth empire.