Settings icon deleted accidentaly from iPod touch
Are you certain you didn't just accidentally put it in a folder? It's impossible to delete, as you note.

You can determine if the app is still there by sliding springboard to the right until the spotlight search pane is revealed. Type "settings" and if the app is still installed it will appear in the search results; tapping on the result will launch it.

If it still shows up in spotlight then it's there on your device somewhere. The other possibility, if it's not in a folder or you're otherwise just missing it, is that all 11 springboard pages are full of app icons and you somehow accidentally moved your Settings app to the 12th page or beyond. In that case, group some apps into folders and, if necessary, sync with iTunes, at which time the icon will become visible again.