The stats suggestion is a good, Contest-centric one, but I think an actual Pokemon would be the most help to newbies, and by limiting it to Contests until they have all Division Ribbons they have a real incentive to do Contests, which helps out the board.
Still, WTP is right and we don't want to give out free Pokemon. I think if this gets implemented, it should not be redactive (i.e. current members can't claim one), and maybe the Pokemon's rank should be capped at like Medium or Hard. Also, what Siless said - definitely untradable.