Well, first off, welcome to the wonderful world of arduino! I’m no pro but my skills are moderate enough that I suppose I may be of help. To answer your questions (and ask a few of my own):
Are you absolutely sure you would be unable to receive any internet-ordered boards? There are a ton of sites that offer every flavor of arduino to get you started with prices ranging anywhere from $10 to $60 for a board or the necessary pre-bootloaded chip w/ component combo.
(my personal favorites: sparkfun, seeedstudio, and nkc electronics)
yes, the atmega 168 is the original compatible chip for the first-gen duemilanove. In order to program the chip you will need an avr programmer which can either be homebuilt (though you will need access to a computer with a serial or parallel port) or you can buy a programmer for $$ check out adafruit.com or sparkfun.com for more info on that.
for programming tips I would poke around the forum for some other posts and tutorials as many people have done this before, though, I am not among those homebrew few.
you should check out:
When using the true arduino platform you will be using the processing/wiring language defined by the arduino IDE. The language is very similar in structure to java and c++ and relatively simple to learn in comparison to most programming languages.