Altavista and others beside were already crawling the web.
Yahoo and Dmoz were curated but Google definitely wasn't the first crawler.
As for the approaches being victim to keyword stuffing: that was because the algorithms used were exclusively 'on page' without assigning a value to links.