Originally they were people from the Abyss colony who were for one reason or another expelled from the colony (the reasons given in the Memoirs of Sir Cabirus are suspicious) and instead of going back to the surface have ventured deeper into the Abyss. There the dark powers of the place started to mutate their bodies, resulting in them becoming the green-skinned Exiles.
People in the Abyss call them Ghouls, but this is clearly a misconception. A Ghoul is a brainless, dead body, animated by magic powers. The Exiles however are well alive and also have the needs of a living being, as proven by the fact that they still need to eat (otherwise it would impossible to bribe various Exiles with fish).
The Avatar met them on the fifth level of the Abyss in Ultima Underworld I, where most of them could either give hints or create some unique items. After the destruction of the Abyss colony, it is not known if they had been able to re-integrate into the society of Britannia or were killed because of their nature.