You aren't allowed to use existing music unless you got permission from the original composer (or his/her publisher), even if it is not the original recording.
As a band you are allowed to play covers of songs on stage without having to ask permission or anything.
When you record a cover of a song, it goes the same as above: You have to get permission from the original composer or publisher.
Hope this helps!