I have a Paladin, now level 2, and at character creation, I didn't exactly have a ton of skill points to set. I have -1 in INT and I'm not a human, so that left me with quite little choice. This campaign has only my character and a druid (plus his wolf).
At one point, we came across a prison cell in an underground cave-building-thing with a ghoul and, most importantly, a chest and a bookcase in it. We shot the imprisoned ghoul down and then looked for the key to the cell, without success. The bars were thick, solid metal and they came out of solid rock. After trying to destroy the lock's mechanism, it became clear we could not force our way in, and we left, frustrated, since that prison cell would have contained the only treasure the whole dungeon had.
Then we knew that lockpicking (Open Lock skill) would be very useful. After all, not all doors will conveniently be easily broken wood and a locked metal box would screw us over. I looked everywhere I could, but I did not find a way for me to learn Open Lock, a non-class ability for which untrained checks aren't allowed.
I have two questions regarding this:
Assuming I had at least 10 in INT and thus would get 2 skill points per level instead of 1, would it be possible for me to suddenly put a skill point in Open Lock? If so, my druid companion could learn the skill since he gets 2 or 3 skill points per level (not sure how low his INT is). How could that be justified in a realistic way, since there's no master rogue to teach him magically as soon as he reaches level 3?
In a situation where you only get one skill point per level, is there a way, any way, to become capable of opening locks without a key? Could I find an expert in town who could somehow teach me basic ability (thus making the skill one in which innate tests are allowed for me) regardless of my inability to put points in the skill?
Additional note: For now at least (the DM will see when we reach higher levels), we're not using any "add-on" books. Only the master's, player and monster books. And maybe an extra monster book or two, not sure, that's a mystery that stays behind the master's screen.
Don't hesitate to ask for more information in the comments. We're playing in French, and many game terms vary wildly between the original English version and the French translation (just look at the armor list for instance), so I may have made up stuff there.
In short, you may invest one skill point or odd number of skill points for an untrained cross-class skill. You have only half(1/2) rank for that skill. Mechanically, you don't have any advantage over untrained ones, but in your next level, you can invest one more skill point in the skill, making that a trained skill so that you are allowed to try the skill.
For justifying how exactly did you get the appropriate training, the Player's Handbook or SRD says nothing about justification in role-playing aspects. You simply get the skill points, and justification is up to you. You can say that you analyzed broken locks' structure by taking a glimpse at it, got a bobby pin and practiced with it so many times, or you suddenly became an apprentice of a rogue. Oh, you are a paladin, so maybe your deity have taught you with the necessary skills in your dream!
P. S. As @KRyan have said, the appropriate skill name for your intended action is "Open Lock". Be sure not to confuse it with "Disable Device", which is for trap jamming!