Well how hard is it to take a human graphic from a mod like HoTK and fiddle with it to make it look non-human? I don't really know enough about how the graphic skins are created to know how much they can be fiddled with.
Doing a quick search for different humanoids, I think the best bet would be to make them look like the Japanese Oni.
http://en.wikipedia.org/wiki/Oni_%28folklore%29
Now I'm thinking of only taking the look, not the lore behind them. Although perhaps the original Oni where human but tricked by Agares (or someone) and became corrupted over time similar to how orcs are a corruption of elves in Tolkien. I mean during the Age of Ice, you'd have a lot of desperate people.
I'm thinking of some thing in the sense that they are 'possessed' in a symbiotic way by damned souls. Even in death, you are reborn to fight and kill another day. This merging of new souls w/damned souls results in the larger bodies, horns, fangs and red skin.
I would think this would be a race that would sort of have the opposite problem with war weariness - to much peace would cause strife.