Really? Mine restores fine without an internet connection. It should, at least this it what it's done for me, search for the latest firmware on Apple's servers, check that your iPod is up to date, then:
a) update the iPod and restore if it's using old software.
b) merely restore the iPod if it's up to date.
If it can't find the update server (in other words, if you don't have an internet connection), it should come up with a dialog stating that "there was an error downloading the update, this iPod will be restored using the old software".
Unless it's something they've removed in the latest version of iTunes...
