I went with a Human (an often maligned cleric race) cleric that was split between STR and WIS as the two prime stats with a score of 16. This was so I could choose between either STR or WIS for attack powers for flexibility. CHA I didn't worry about so much, but I still maintained a positive bonus with a score of 12. So instead of pumping up CHA, I went ahead and made CON my tertiary, as I wanted to qualify for heavier armor feats. The added benefit of having a better HP base and healing surges was also a bonus.
Since my human cleric is so versatile stats wise, I can use Scared Flame and Laser of Faith at range, and use Righteous Brand for melee. Having a mediocre Charisma will hurt some power bonuses down the road, but I feel that the flexibility of having both high STR and WIS make up for that.
For feats, I am going for survivability, since clerics, both devoted and battle variants, are always within one movement action of the front line. So I took Scale Mail as the first feat, and then for the second feat (human, remember?) I opted for a reach weapon. With a reach weapon, I could still engage the enemy with my melee powers, but I could do so from the relative safety of hiding behind the defender by attacking through his square to get to the enemies.
As it looks right now, this character will have Action surge for the level 2 feat, and when stats are able to go up, one point will go to Con in order to qualify for plate mail at level 4.
Try a hybrid character! Having a good CHA score is helpful, but it's by no means a deal breaker