One thing to note is that not all skills are mental: there's Athletics, Acrobats, Thievery, etc (just off the top of my head). Instead of awarding bonus skills for high Int, you could rule that if a player has a +3 or better bonus in a stat, she can choose to be trained in a single extra skill whose bonus comes from that stat (Athletics = Str, Acrobatics = Dex, etc.).

A high stat obviously already help any skill which uses that stat as a bonus, and it's likely that e.g. a high-Str character will already have a relevant skill like Athletics. But it would give nearly every character a single extra skill which will be relevant to the class.