Here's the secret:
None of these puzzles are difficult. In each puzzle, there are only finitely many possible scenarios (in the most famous two guards and two doors puzzle, there are only four possible scenarios, and in the gods puzzle you describe there are only 72 possible scenarios). Questions you can ask can be classified by which scenarios result in a "yes" answer, which scenarios result in a "no" answer, and which scenarios result in a random answer (or "da"/"ja"/random). That means that the number of functionally different questions you can ask is at most three raised to the power of the number of scenarios (and in practice it is a lot smaller, since you can take advantage of various symmetries of the problem). Now just check each type of question in order, and see which one works. If you get to ask several questions, then the number of possible strategies increases, but again a brute force approach will eventually get you to a solution.
For instance, here is the complete idiot's method of solving the standard two guards/two doors puzzle (one lies, one tells the truth, one door to freedom, the other to death, one question):
First we name the scenarios. Let's say FT is the scenario where the left door is freedom and left guard is truth, FL is the scenario where the left door is freedom and left guard is lying, DT means left door is death and left guard is truth, DL means left door is death and left guard is lying. Taking advantage of a symmetry, let's decide from the very beginning that we are going to ask a question to the left guard. Since questions only have yes/no answers, there are really only 16 questions we can ask. We'll classify questions by the collection of scenarios that lead to a "yes" answer from the left guard. First we have: "Are we not in any scenario at all?", which is answered with a yes in scenarios FL, DL. Second we have: "Are we in scenario FT?", which is answered with a yes in scenarios FT, FL, DL. Third we have: "Are we in scenario FL?", which is answered with a yes in scenario DL. Fourth we have: "Are we either in scenario FT or scenario FL?", which is answered with a yes in scenarios FT, DL. And so on... Our goal is to find a question which has one answer if the left door is freedom and has the opposite answer if the left door is death. Going through the list, we find that there are really only two questions that work: one is "Are we either in scenario FT or scenario DL?", which is answered with a yes in scenarios FT, FL, and the other is "Are we either in scenario FL or scenario DT?", which is answered with a yes in scenarios DT, DL. Either one of these questions solves the puzzle, and can be rephrased in other ways to make our thought process less obvious (e.g. "If I asked you whether this door lead to freedom, would you say yes?" is really the same as "Are we either in scenario FT or scenario DL?", but it sounds much cleverer).
In questions where there are no random answers and we are looking for one piece of information with one question, there is a slightly cleverer method:
Say there are N possible scenarios, numbered 1, ..., N, and we want to know if statement X is true. In each scenario, write f(i) for the answer you would receive in response to the question "Is X true?" in scenario i, and write g(i) for whether X is actually true in scenario i. Suppose, for example, that N is 4, f(1) is "da", f(2) is "ja", f(3) is "ja", f(4) is "da", g(1) is true, g(2) is true, g(3) is true, and g(4) is false. Let's say we want to come up with a question where if we hear the answer "ja" it will mean that X is true. Then we make the question: "Is it true that we are either in scenario 2 or in scenario 3 or in scenario 4?", where we include exactly scenarios i where either f(i) is "ja" and g(i) is true, or f(i) is "da" and g(i) is false.
When there are random answers, it is a bit trickier.
From the point of view of information theory, when there are no random answers one well-chosen question should always get you exactly one bit of useful information. In the presence of random answers, you have a chance of getting a useless answer to your question, so you get slightly less than one bit per question. By phrasing questions correctly, a truth-teller and a liar become equally useful to you, so the challenge is to ask a few questions at the beginning in order to identify someone who is not a random answerer so that you can ask that person the last few questions and extract the information you are after. In any situation where there are at least as many random answerers as truthtellers/liars, you have little hope, since the random answerers could "randomly" end up acting exactly as if the roles were reassigned with them as all of the truthtellers/liars and the real truthtellers/liars as random answerers (of course in the puzzle you describe, in the bad case where there are as many randoms as truthtellers/liars the answer is just that there are two random answerers, so it is still solvable). If there are more truthtellers/liars than random answerers then you know that with enough questions you can manage things by, essentially, taking the majority opinion (and phrasing questions appropriately to make liars behave like truthtellers). Then you just brute force your way to the most efficient (and cleverest sounding) strategy.
Edit: How I would attack your puzzle:
Obviously it would take a while to do a pure brute force, so let's try being at least a little clever. First let's try the variant where everyone either tells the truth or is random, and we want to know whether there are one or two randoms. If we ask our first two questions to the two randoms, they can give any possible answers, so we need at least three questions. In fact, if we only ask three questions to two randoms and one truthteller, then the two randoms could pretend that they are truthtellers, that the real truthteller we asked is a random, and that the remaining god is a truthteller, fooling us. So we need at least four questions, and we should talk to all four people. If we ask everyone whether there are one or two randoms, then in the case of one random god we hear "one", "one", "one", and something random, in some order, while in the case of two random gods we hear "two", "two", and two random answers, in some order, and we can tell which scenario we are in regardless of how the random answers come out. So we go back to the real problem. We can make the liars act like truthtellers by asking questions like, "Is it true that either you are a truthteller and there is one random or you are a liar and there are two randoms?", so with four questions we can determine whether there are two randoms. If there is only one random, we can determine how many liars there are by taking majority opinion on a question like, "Is it true that either you are a truthteller and there is one liar or you are a liar and there are two liars?", so eight questions is enough to get by. Eight is a lot, probably we can do better. When we are polling for the number of randoms, if we hear two people confirm that there are two randoms we can stop right away, and if we hear three people confirm that there is only one random we can move on to determining who the liar is right away. If we've determined that there is only one random, we know that anyone who acted like there were two randoms is a random trying to fool us and we can ask someone else a single question to determine whether there are one or two liars (five questions used up in this case). If the lone random plays along and acts like there is only one random, then we only spend three questions determining that there is only one random, but we don't know who the random is yet, and a majority opinion from any three gods tells us whether there are one or two liars (six questions used in this case). So we can get it down to six questions, but it still feels a little wasteful. This solution is getting a little long, so I'll leave it at that for now...