The Wikipedia entry on Cloud Computing traces the origins of the idea back to considerably before the emergence of the internet:
The underlying concept dates back to 1960 when John McCarthy opined that "computation may someday be organized as a public utility"; indeed it shares characteristics with service bureaus which date back to the 1960s.McCarthy, generally credited with coining the term "Artificial Intelligence", apparently raised the "public utility" idea in 1961. But I suppose that the basic idea can be traced back even earlier. It must have been swimming around in some primordial global brain well before computers, but the necessary infrastructure to make it feasible has only now truly materialized.