Photo restroration is quite an easy task just very time consuming, which is probably the reason you have no replies sofar. this one took 2-3hrs to this stage and needs at least another couple hrs to finish.
Here's some tips:
Scan at highest resolution possible (regardless of print output dpi).
Get yr hands on photoshop - doesn't have to be latest version, even V5.0 has all the features you need - and its not that big of a learning curve.
Use the clone tool with a mix of round brushes (sharp and with feather) small sized with phot zoomed right in. You may find the healing brush useful but I don't.
Like i said its painstaking so don't expect instant results just whittle away at it with the clone tool.
If you have any questions just ask here
good luck.