This Footytube forum discussion mentions several players (most French) from other countries: Zidane (Algeria), Desailly (Ghana), Vieira (Senegal), that went on to not play for their country of birth. The decision by Algeria to not accept Zidane because he was too slow sure turned out to be a poor decision, 'eh?
One other that comes to mind is Dani Osvaldo, who plays for Italy but was born in Argentina (a common relationship for the two countries).
The aforementioned Kevin-Prince (Germany) plays for Ghana and played against Germany.
Unfortunately, none of these players have scored against their countries of birth as far as I can see scanning their International Goals, but the chances are high that each played against their country of birth (all three French players have many, many caps for Les Bleus)
Players who play against their national team:
David Trezeguet (Argentina): at least played a game against Argentine (playing for france).
Guillermo Franco (Argentina): Plays for Mexico, and plays at least two times against argentina. One he didn't enter the field, and the other he enter as a substitute. The two matches where on world cup (2006 and 2010)
Player who didn't play against his national team:
Alfredo Di Stefano (Argentina): I can't find any reference if he plays a match vs Argentina when he was playing for Spain.
Camoranesi (Argentina): didn't play against Argentina, when he was playing for Italy.
After looking at this list of players who have switched nationalities in football I saw that Mathias Fernadez represented Chile despite being Argentinian. In a game in 2011 he scored vs Argentina. He does however consider himself Chilean having left Argentina aged 4.