What you describe sounds just like Populous (Populous - Wikipedia) from Bullfrog games. Perhaps it was called something different over your side of the pond? It was designed by Peter Molyneux - who later went on to do Black and White.
This person is apparently doing an open source implementation. Don't know if its any good.