I would do one of three things, but take your pick
A: If starting at level X (in your case 3), bar any ELC X or higher. Only allow ELC X-1 or lower
B: My DM changed deep gnome to ECL +2 for me (I don't know why, but he did)
C: Aprentice level. If the deep gnome was a rogue (for example), he would get BAB +0 F/R/W 0/1/0, rogue weapon and armor profeciencies, 6+con modifier HP, 8+int modifier for skills, and a 1st level feat.
When the deep gnome had enough XP to be a 4th level charecter, he would have 1 class level, and gain the rest of the rogues abilities: +1 to reflex, sneak attack 1d6
D. Start at 4th level.
Personally, I'd offer C if they wanted to play a deep gnome (mostly cause I like them a lot), cause I personally wouldn't raise the starting level of the group.