Are perimeter searches without consent nor warrant ever legal?
What if it's a motor vehicle / car? Is the situation different with a house?
Huge difference between a car and a house. For example, at least in Pennsylvania no warrant is required to search a vehicle on public roads. In other states there are so many easy pretexts that you practically have little protection from a full vehicle search (although the pretext will have to withstand strict scrutiny if evidence found in a search is used to charge you with a crime).
Your house, on the other hand, still enjoys very strong fourth-amendment protections: One of my favorite U.S. Supreme Court cases on the subject is Florida v. Jardines, in which SCOTUS ruled that even approaching the front door with a drug-sniffing dog without a warrant constituted an illegal search. (The majority opinion is worth reading for its illumination of current law on this question.)
Depends on what you mean by "perimeter search". Police can, for example, walk around the perimeter of a car or house if they have permission or the right to walk where they're walking (e.g, in your next-door neighbors' yard) If, while walking, they see evidence in your yard that you committed a crime, they can walk over and seize it (see http://www.olemiss.edu/depts/ncjrl/pdf/Law%20Enforcement%20Materials/Plain%20View%20Doctrine.pdf for more info on the plain view doctrine)
If a K9 is lawfully walking with them, and the dog smells evidence of illegal activity on your property, the police can legally act on the dog's alert.