Megalon is an Earth monster, no denying it. All of the metallic parts are composite minerals and all the functions are quote-unquote "natural" (by Toho standards). The only place you'll hear that Megalon is a space monster is probably from online fan fiction.
Gigan... Oh Gigan, how dafaq did he come about? Probably the best part of it is that we'll never know; some mysteries are best unresolved. However, I do have my personal theory on what Gigan
could be.
Could it be entirely possible that Gigan is related to King Ghidorah? Not in the sense that they're siblings or offspring, but Gigan being some subspecies or an off-shoot of Ghidorah. They both share the golden scales for one. But I guess that it could just be coincidence with any monster, really. But the other point is how Ghidorah and Gigan continue to team up, even after the Godzilla Tower was destroyed. Granted, I don't recall Ghidorah doing much after he was freed (been a while since I've seen the film in its entirety, so my memory is a bit hazy), but the fact that he didn't attack Gigan should be taken into question (though the two did need to get through some Earth monsters, so a common threat I suppose).
As I said, this is merely speculation. I'm more than sure that there are a couple of holes here or there or that it's merely coincidence. Until Toho sheds light on the matter, Gigan will forever be a true mystery.