The reference does suggest using randomSeed(analogRead(0)) (or some unused analog input).
On a 328 you also have analog(8) to measure internal temperature, but it is not reliable random - http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1294239019 - but it might be good enough for your application. It won't cost you a free pin as it is internall so allways free....
If your application has a ethernetshield you might consider fetching the serial number from a simple PHP script on a local website or a randomnumber from www.random.org.
Imho: Sometimes it is much easier to solve things with some extra tools than try to build it all in one sketch.