I think the Teahouse model could work really well. New contributors and greeters could create profiles that has information about them, their skills, their interests, and their IRC nicks.
These profiles could help new contributors find a new greeter. I think users would look for greeters with similar backgrounds to ping on IRC, and I know that new contributors would likely have questions that many people could answer, so I wonder if it would be an issue of a few greeters getting requests for help from a number new contributors when other greeters are able to help them as well. I think I'm getting ahead of myself, though.
"Greeters have an explicit interest helping contributors that find a harder time...": Also, these profiles could probably help Greeters identify those new contributors that generally have a harder time.