Re: the companions always being human. Sorry, but that's a ground rule that was established from Day 1 (in fact - someone feel free to correct me - I think it's even spelled out in the original series bible. And I'm talking about the one from 1963). It's part of the formula. K-9 would never have worked as a solo companion, and even if the prop had worked, Kamelion would have only served as a compliment for the other human characters.
Nope. Nonhuman but humanoid companions include Susan (Gallifreyan), Romana (Gallifreyan), Adric (Terradonian born on Alzarius), Nyssa (Trakenite), and Turlough (Trion). The Fourth Doctor was without a human companion for three whole seasons, between Leela's departure at the end of season 15 and Tegan's joining at the end of season 18. And since Leela wasn't from Earth but from a lost human colony in the future, the Doctor went over four and a half seasons without an Earthborn companion.