As far as I know, racial spells aren't actually defined anywhere, and so the following answer is entirely my opinion, well-reasoned though it may be:
For your examples, the answers are yes, yes, yes, and no.
Racial spells are only considered "default" or commonplace for characters of those races. This means that a human wizard can't select aboleth's lung as a "free" spell when leveling up, and that a human sorcerer could only select it if they had access to the spell somehow (such as studying with a spellcaster who had it). Divine casters would need to be at least made aware the spell exists before they request it from their deity. Basically any other means of learning a spell besides just leveling up should remain valid:
- Learning the spell from a scroll, spellbook, or other spellcaster
- Researching the spell independently
- Identifying the spell as it's cast with a Spellcraft check (for casters who only need to be exposed to the spell, like sorcerers and most divine casters - this isn't comprehensive enough for a wizard to add the spell to their book0
- Suffering the effects of the spell (for caster who only need to be exposed to it)
- Learning about the spell from a magical source, such as speak with dead or via an outsider
All of these things constitute "GM permission". If the GM doesn't want you learning the spell, all he has to do is not introduce a gillman wizard with aboleth's lung in his spellbook. Not already knowing the spell exists, you couldn't really call up a water elemental or devil to ask about it directly, and the GM is in control of spell research as well. Buying a scroll of the spell is impossible if no one knows it to scribe them in the first place.
If the GM doesn't mind you learning it, then it's safe to assume that the spell has made it out of its circles and into a more general curriculum. It could be anywhere from as hard as actually going to a gillman village and buying a scroll (for an inflated price, even) or as easy as simply choosing the spell on level-up, depending on your GM.