I had always thought the name was taken from the phrase "out on the Greenman's" which meant beyond the edge of town, beyond the cultivated fields. It was the place the pagans, or more precisely, heathens - retreated to when the Christian churches came in. If you lived on the Greenman's you were living in the rough, and it was not uncommon for heathens to use leaves and foliage for camoflage. Sometimes they were hired by the townies to police the woods and keep out strangers and highwayfolk. Later on, as cathedrals became more ornate, these heathens would be depicted on the outside amoung the gargoyles to protect the cathedrals as they protected the towns.

If there was a god involved, it may have been Herne the Hunter - who used to camoflage himself.

When I lived in Germany as a teenager, a lot of the farmers near Heidelberg seemed to think that the greenman was a way of hiding images of Pan on the cathedrals in plain sight. The leaves originally were the grape leaves pan wore. Eventually the leaves became more generic and less grape like.
Much of the craft of cathedral decoration was devised to try to bring the heathens around to the new, better way of the church (better in the eyes of the church)