The most important factors in getting a small animal internship are GPA/class rank and references, both letters and informal references. Since by 4th year, your GPA is pretty much mathematically set, Ill focus on the references.
References should be from clinicians that youve directly worked with. Internships are clinical positions, so references that can address your clinical skills are better than someone like an anatomy professor or a researcher you did bench research with. The reality is that someone can do great in anatomy or research and be lousy in the clinics.
For internships, the specialty of the reference doesnt matter (it does matter for residency). If youre looking at small animal I would focus on small animal faculty, but if you had a large animal clinician that would write a glowing letter thats fine a good clinical student is a good clinical student. In general, focus on faculty, not residents or interns who wont carry the weight of experience in evaluating students. On the other hand, dont bother with administrators like deans and assistant deans. Everybody knows that at most schools they dont interact with the students in the clinics.
Start now. The obvious choices are clinicians that gave you a good grade and comments and those you feel you developed a rapport with. Anyone who said something like, You know, you should apply for an internship. is a good choice.
As for asking them, always start with something like, Do you feel you worked with me enough to write a good reference letter? This gives them an easy out if they dont feel qualified or more importantly if they dont feel they can write a good letter. At any hint of reservations, get someone else. A single poor letter is the kiss of death.
Although most of the references should be from your school, if you did a clinical externship somewhere and can get a good reference from there, thats excellent.
Regarding visits and interviews, while nobody has the time or money to visit all the places they are interested in, I would try to visit as many of your top choices as possible. First, this is the best way to find out if you will like it there. Internship is stressful enough at somewhere you like, its absolutely miserable if youre somewhere full of jerks. Second, making a really good impression at the visit, can move you up in their ranking. Realize that a few schools really discourage internship visits so if you run into that, dont take it personal.
Even better than an interview is to do an out-rotation or externship. Most people can come off as reasonably pleasant for a few hours but its really tough to fake it for several weeks on a clinical rotation. Blowing everyone away on an externship is one of the few things that can make up for less than stellar grades (which is obviously not a problem with 3.96).