While Bill may have popularised the term permaculture, here are few things that I read before I came across his work, that were equally relevant.
1. The Web of Life by John H Storer
http://www.amazon.com/Web-Life-first-Book-Ecology/dp/B00005X589 One of the first authors to recognise and describe ecology as a web formation. Seems obvious now. but this is still an interesting read, especially if you are in North America.
2. Food in Civilisation - Carson L A Ritchie
http://www.amazon.com/Food-civilization-history-affected-tastes/dp/0825300371 Long before The Omnivore's Dilemma here was a fascinating history of food.
3. Subdue the Earth - Ralph Franklin Walworth
http://www.amazon.com/Subdue-Earth-Ralph-Franklin-Walworth/dp/0440084342 Not strictly permaculture but some interesting theories about the formation of the Earth. This is the kind of book that helps you get into contrarian thinking mode.
4. An Operating Manual for Spaceship Earth - R Buckminster Fuller.
http://www.futurehi.net/docs/OperatingManual.html http://www.amazon.com/Operating-Manual-Spaceship-Buckminster-Fuller/dp/3037781262 Mollison gives Bucky no credit whatsoever and yet his ideas crop up over again in Permaculture. Bucky was pulling permaculture ideas together before Millinson was even born. Essential reading.
5. Energy and Equity - Ivan Illich
http://www.preservenet.com/theory/Illich/EnergyEquity/Energy%20and%20Equity.htm http://www.amazon.com/Energy-Equity-Ideas-Progress-Illich/dp/0714510580 Long before anybody even mentioned peak oil, Illich had nailed the energy problem clearly and succinclty. It will be a while before anybody betters this work.
Hope that these help and inspire.
Chris