Having icons mounted on headstones is extremely common, and completely permissible within Orthodox tradition. I have seen many examples of graves of married couple, where an icon of Christ is on the husband's side of the grave, an icon of the Mother of God on the wife's. Lovely gesture, mirroring the Slavic custom of bestowing of wedding icons to a newly-married couple. In many other cases, an icon of the deceased's patron saint is used. Let us also remember that when gravesites are tended by family or friends of the departed, it is common practice to cross oneself when arriving at the grave and on leaving it, and incense is frequently burned during the time spent while the grave is being tidied, flowers arranged, or spent in contemplation. Graves also places where the trisagion/short panikhida is served by a priest, so why shouldn't icons be there?
To prevent weathering or fading of icons made of conventional materials, the simple solution is to have the icon printed onto a porcelain plaque, which will survive quite happily even if exposed to the elements. These days, it is a relatively simple process, not as expensive as it used to be, and full colour can be used. The same process has long been used to produce "permanent" photographs of the deceased.