I got a Rush Attack bonus on a bracelet (from a chest) on level 5 or 6. Skill bonuses start becoming more common (though still relatively rare) about level 9 or 10; I didn't notice a significant difference between shop and random loot occurrence. I've also had Jump Attack, Ranger Strength, Summon Ghost and a couple others I don't recall specifically (I have not seen Lockpick yet, though).
