Based on the stats of the Rhodin warrior on page 408 of AE, I'd put them at +4 Strength, +2 Constitution, -2 Intelligece, -2 Wisdom, -2 Charisma. Darkvision, and a racial natural attack (headbutt). No racial HD, no LA. While the mental penalties are steep, it does balance out to +6/-6 overall, so I see no problem with allowing them, so long as it's pretty well understood that Rhodin characters are almost universally going to be big dumb fighters who are attractive to people who just gotta have that +1 more to hit and damage.
Looking over their cultural information, I gotta say that the triple mental penalty makes a lot of sense. They have no culture, no appreciation for their environment or for greater powers, no technology beyond what they have stolen, and are pretty much useless unless they are led by a Skurg. They're actually a step down from Orcs, who have arts (Cha), crafts (Int), tactics (Int) and some form of religion or spirituality (Wis). If you ask me, they're getting off lightly with a -2 compared to their flavortext.
Generally, any Rhodin PC is probably going to be an ex-slave, mercenary, or tribal exile, who tried to fit into the Diamond Throne's culture (or whatever setting your using). In my own homebrew, Rhodin are generally mercenaries serving with invading armies, rebel groups, pirate crews, and mafia families, all of whom can make use of big, dumb monsters who can tear people's arms out of their sockets. Your mileage may vary.
Robert "Warhammmer Beast-men for D20" Ranting