In Dune Messiah Frank Herbert states that "there exists no separation between gods and men: one blends softly and casually into the other" yet in Science Fiction and in Fantasy there exist a number of distinct "power levels" if you will; "human", "superhuman", "weakly godlike", etc... So my question is are these actually hard definitions with distinct criteria or are they simply the product of attempts to put labels where they don't belong or can't be consistent? In particular if someone can point me at a scale that separates these levels along firm boundaries I'd be very interested.
I'm not sure how this question can be appropriately answered without using an opinion, but I'll at least tell you why that is. There is no scientific or even societal scale separating gods from men because gods are a matter of faith (or fiction, as many would say). There existence is a mere opinion, thus has no place in scientific discourse. If, however, you want to know how they are separated in fiction, that is still going to be impossible to quantify. Since the gods in our works are fictional (just as some would say the god(s) in real life are), the rules are up to the author. There is no sliding scale between god and human because science has no proof of gods, much less a few gods lying around they can study to separate from human beings. Most answers to this question will be completely opinion based.
Divinity has nothing to do with power level. It is fully encompassed in how holy others view you. There are many divine creatures without any special powers in stories. There are also Gods who never uses their powers in the eyes of humans.
Just because someone is super powerful or can perform miracles does not really make them a god. Only when other people worship him does he actually become said to be a god. Godzilla isn't a god just because he is immortal and indestructible and can level cities, all of those qualities actually put Godzilla above the power level of many contemporary gods. However, if people started worshiping Godzilla, then Godzilla actually can be called a god. The reverse is true with god kings, they are technically physically only human but they make people worship them as more than that and thus, they are then regarded as gods or descended from gods and are thus divine.