Mechanically, if the level-up happens while the party is out adventuring, nothing prevents any character from advancing any of the existing skills by a number of ranks.
That means that the low-intelligence fighter can theoretically gain ranks in Knowledge(Arcana) or Spellcraft mid-dungeon and become moderately competent in it. With no trainers, no materials to learn from, no time spent, no nothing.
Furthermore, if the skill being learned is Linguistics, than the character also gets to learn a whole new language. And the ancient obscure ones are no harder to learn than the modern ones.
I have encountered GM's that will outright ban that mechanical possibility because they consider that implausible.
What is the best most defensible in-story justification that can be given for characters learning to use trained-only skills on level-up?
The quality of the justification can be hard to measure, so I'll try to outline some arbitrary constraints:
We'll say that the justifications that require prior in-story preparation by the player are worse than the ones that can be used even if the player decides to take the rank the moment the level-up occurs.
The setting-independent justifications are better than the ones relying on specifics.
General ones that can be applied to all skills at once are better than arrays of different justifications for different skills.
The less "But what about/if ?" questions the justification raises - the better.