Do video stores have to get permission from the copyright holder to rent a movie out?

Answer 1

Not at all. The first-sale doctrine says that a person who owns a legal copy of a copyrighted work can dispose of it in any way he/she sees fit, including giving, selling, or renting it away. Exceptions exist for music recordings and software.

Answer 2

That is assuming that what you rent out is a normal purchased factory made DVD or tape. Those royalties are paid by the manufacturer upon distribution. Pirates, downloads and copies used for commercial purpose will get you in trouble because distribution royalties have not been paid.