Knowledge(Religion) is a tough one, and with those parameters its even harder. The Educated feat would save you all of the cross-classing waste. Apprentice(Spellcaster) for a wizard apprenticing a sorcerer or a cleric apprenticing a druid would work, which would give you 1 knowledge and UMD on your spell list, as well as some spell swapping. For elves, Aereni Focus would work: it both adds the skill to your skill list and gives you a +3 bonus, counting as skill focus. In my games, I allow the 3.0 version of cosmopolitan, which is similar, but is available to anyone, only a +2, and doesn't count as skill focus.
As for small races that fit your requirements, Strongheart Human Halflings have Favored Class: Any.