Many (most?) countries do not extradite their own citizens, that's really not specific to rogue states. Some countries will prosecute their own citizens instead but that's not always easy to do in practice.
It's important to realize that international law is generally messy and based on consent from each individual state. Interpol does not have nearly as many powers as frequently pictured in fiction and even with an extradition treaty in place it's not trivial to have someone extradited. It's all very ad hoc and imperfect so yes, it's often a case of “tough luck” and not only with North Korea.
Whatever the problem, the only real recourses are the usual diplomatic actions: Official complaints, summoning the other country's ambassador, pulling one's ambassador, breaking off relationship, etc. In most cases, a country will not escalate the situation for a simple criminal case.
In your particular example, the country of the victim could certainly initiate proceedings, start gathering evidence immediately, issue arrest warrants, possibly go as far as judging the suspect in abstentia (I don't think Germany does it but other European states do or at least did until very recently). It will be difficult to actually carry out any sentence but it will severely restricts the perpetrator's ability to leave his refuge.
Here is another prominent case illustrating this (and unlike Snowden, it's not even about Russia and spies, it's about France, Switzerland and the US and a run-of-the-mill criminal case).
Also, North Korea is a particularly restive state so I have no idea how they might react but “rogue”, failed or authoritarian states are not especially protective of their own citizens. Obviously, they might refuse to do anything just to be seen resisting pressure from the outside but unless the individual is particularly well connected, I can just as easily imagine that such a state would welcome the opportunity to score some political points by punishing the suspect harshly or possibly try to turn a potential extradition into some kind of bargaining chip.