When you complete quests, sometimes rare gems and ores are offered randomly as some of the choices for rewards. You might be able to get some malachite gems that way. Or, you might just have to wait till later in the game. I'm pretty sure you'll eventually find some as loot, and when you play Flames of Vengeance, there is a gem merchant who stocks a few malachite gems.
