Hey, welcome to gymchat! And gymnastics! Gymnastics is really lots of fun! :D
For pullovers: don't worry about your height being an issue! Even for giants (going around and around the high bar) where you have to be careful not to hit your toes on the low bar, you can do them the straddle way where before getting to the low bar in your swings you straddle (like middle split) your legs.
--> what helps to get your pullover: strong abs muscles and also strong arm muscles - the legs muscle will help you when you do the pullover the way where you start with your feet on the mat and push off with one leg first (which is the way how most people learn it, rather than the harder ways of doing legs together, or pull-up first and then legs over with no push off the mat - for that you really need really strong abs muscles and arm muscles!!), but you still need strong abs and arms muscles too. Conditioning that helps the most probably for getting your pullover: push-ups, pull-ups, and v-ups (which are really good to get your kip, which is the next step!) To make the push-ups harder you can put your feet up higher like on some mats when you do them, to make the pull-ups harder you can add 5-lb pair weights to you ankles or your waist (they're ankle weights, but you can connect the velcro together and put it around your waist). Leg lifts are also good for abs - do you get them all the way up yet, or like horizontal? Takes time to get them all the way up usually, so don't worry. You probably have good leg muscles from ice skating right?
For private lessons, you could take a look before or after your class at the different coaches when they are coaching and see who you think you would like to work with - it's usually open to whoever you want to ask. Personally, I like to have coaches who I can trust to spot me and also who are experienced and know what they're doing - so that's usually the head coach or higher level coaches, and male coach, especially if you're not a little kid, you know, who like everyone can spot! :D Private lessons cost differently depending on where you are, but are like around $40-$50 per hour, maybe $60 I think. If you ask for multiple privates, like for more than just once, maybe they would be open to giving you a better rate. There's a thread on private lessons/costs on this message board actually.
I heard about people starting ice skating because they were sick and it helped, like Scott Hamilton. What's the reason, the fresh ice air with exercise?
p.s. running would help with stamina for tumbling and routines, etc. and of course for vault :D Conditioning is really important and can help you get your skills a lot faster. ...and so is good coaching of course! :D