Since this answer will probably need occasional updates, I have made it community wiki.
The post is compiled from these sources:1
Below is the list of players having more goals than caps which have played at least 25/50 international games.
25+ caps
- Poul Nielsen (Denmark) 1.37 (52 goals in 38 games)
- Gunnar Nordahl (Sweden) 1.30 (43 goals in 33 games)
- Sven Rydell (Sweden) 1.14 (49 goals in 43 games)
- Ernest Wilimowski (Poland, West Germany) 1.13 (34 goals in 30 games)
50+ caps
- Sándor Kocsis (Hungary) 1.102 (75 goals in 68 games)
- Gerd Müller (Germany) 1.097 (68 goals in 62 games)
100+ caps
According to the sources I cited above, there are no players in this category with an average number of goals above 1. The best goals-per-game ratio of any player with 100+ caps is that of Ali Daei (Iran), at 0.74 (109 goals in 148 games).
The players with at least 100 caps and average at least 0.50 can be found in the Wikipedia article: List of men's footballers with 50 or more international goals.
Ferenc Puskás is close to 1 goal per match ratio with 84 goals in 85 matches if we only count his appearances for Hungary. After emigration he also played in 4 international matches for Spain.
Another near-miss is Kunishige Kamamoto (Japan) with 75 goals in 76 appearances.
Also Luis Artime (Argentina) was very close to make the above list, with 24 goals in 25 appearances.
1 See also the comments to Nicholas V.'s answer and the links mentioned there.