Without knowing specifically where this rock came from, it's hard to make a truly educated guess based on this description and photo alone. It may be beneficial to employ a mineralogist and/or someone familiar with the area to help you identify this sample, as I will admit I am neither.
Assuming your broad location attribution of East Iceland refers to the Vatnajökull glacial region in the southeast quadrant of the island doesn't limit the possible lithology a whole lot, as this region includes much of the rift zone containing the most recent activity, all the way out to rock dated in excess of 3 Ma, including both extrusive and intrusive lithology as designated by this map.
The surface of the sample is relatively fresh and well-rounded, likely from ice/water action, and seems to have a small fracture running down the lefthand side as shown in the image. The fact that it is relatively fresh means that there is little possibility that the minerals on the surface have been altered greatly by oxidation or other weathering processes. So most of what you see in the image should be indicative of composition.
I'd love to examine the greenish flecks on the surface with a hand lens, because my initial inclination is to say that they are some type of olivine. (Larger photo here). The color is about right, the texture seems to be right without being able to see it terribly clearly, and it fits within the broad scope of the type of basaltic geochemistry associated with Iceland. The black material interspersed between these crystals looks to be a matrix with no outwardly apparent crystalline structure. The glassy appearance of the matrix and the fact that these crystals look to be less than 1mm in size probably means that the parent material cooled quickly and disallowed further crystalline development in both the olivine and the matrix. I almost completely forget my petrology training but I seem to remember that both Fe and Mg olivine can crystallize in solution before other minerals given certain conditions, which wouldn't rule my theory out.
As for the reddish material, I am less confident in saying anything because I just can't see it that well. However, it looks to be slightly softer than the black "matrix" material purely because it occupies recesses on the countenance of the sample. In a more weathered sample this means little, but given that this sample probably just spent quite a while in the geologic equivalent of a rock tumbler, any surficial abnormalities probably have something to say about the physical nature of the sample itself.
My best guess: an olivine-rich basalt that cooled quickly enough to freeze the matrix as glass before further crystallization could occur.
EDIT 04/18: Does anyone else have input? I don't think my analysis is strong enough to stand on its own.