In the US you don’t need to get the copyright holder's permission to record cover songs, you need to pay for a mechanical license. In the case of live performances you don’t need to get permission directly. The venue is the one that pays royalties to a handful of groups that have agreements with thousands of artists.