Yeah, it has been figured out by various other websites. Also, yes, that assumption is correct as well, I can assure you.
Yeah, around the 13-16 range is when the gym leaders start showing up, but the time where they start showing up with regular frequency is pretty vague. To give some sort of a marker, I am like in the level 60's in my avenue atm (No magna-coil + laziness), & I tend to get one gym leader showing up every two days on average. Not completely accurate, but if you are at Lv16 on your avenue atm, then you have like a good 30-40 levels to to go up by before they start showing up very often, as an estimate.
Nope, nothing. Got the Rare Candy like eight or nine times, but a Master Ball? Nah, no luck.