Skeetendo

Right now, the easiest way to edit music is by using the pokered disassembly.
There are music files for each song that are easy to read and easy to edit, such as the gym leader battle music.

It sounds like you want to add a new song, without replacing an existing song. This is possible, but tricky, due to the way that song headers work.

The easiest way would be to edit this routine that chooses the song to play based on the type of battle:

PlayBattleMusic: ; 0x90c6
    xor a
    ld [wMusicHeaderPointer], a
    ld [$d083], a
    dec a
    ld [$c0ee], a
    call PlaySound ; stop music
    call DelayFrame
    ld c, BANK(Music_GymLeaderBattle)
    ld a, [W_GYMLEADERNO]
    and a
    jr z, .notGymLeaderBattle
    ld a, (Music_GymLeaderBattle - $4000) / 3
    jr .playSong
.notGymLeaderBattle
    ld a, [W_CUROPPONENT]
    cp $c8
    jr c, .wildBattle
    cp SONY3 + $c8
    jr z, .finalBattle
    cp LANCE + $c8
    jr nz, .normalTrainerBattle
    ld a, (Music_GymLeaderBattle - $4000) / 3 ; lance also plays gym leader theme
    jr .playSong
.normalTrainerBattle
    ld a, (Music_TrainerBattle - $4000) / 3
    jr .playSong
.finalBattle
    ld a, (Music_FinalBattle - $4000) / 3
    jr .playSong
.wildBattle
    ld a, (Music_WildBattle - $4000) / 3
.playSong
    jp PlayMusic

As you can see, the game uses 8-bit pointers to the song headers instead of 16-bit pointers. (I know you're new to this, so that just basically means that you don't have very many possibilities for more pointers, and there are so many sound effects in the game that it's basically impossible to add a new song header without replacing an old song header)

So since we can't create a new song header, the easiest way to play a new song is to begin a song using an existing song header and then overwriting the headers pointers to the music channels.

Here's what I mean. Use the routine shown above to add a check to see if the current opponent is Articuno, Zapdos, Moltres, or Mewtwo, and if so, jump to a new routine.
At this new routine, begin playing any song, like the wild battle song, using these three lines:

ld c, BANK(Music_WildBattle)
ld a, (Music_WildBattle - $4000) / 39
call PlayMusic

Then immediately after beginning the song, overwrite the channel pointers like this:

ld hl, $C006
ld de, XXYY ; pointer to channel 1
call Music8_OverwriteChannelPointer
ld de, XXYY ; pointer to channel 2
call Music8_OverwriteChannelPointer
ld de, XXYY ; pointer to channel 3
jp Music8_OverwriteChannelPointer

This should allow you to play a new song that doesn't have a song header and this is probably the easiest way to do it. (Gamefreak themselves used this method for the Viridian City theme, the Rival theme and the Poke Flute-in-battle song)

You would have to code in a routine that does that.
So yes... you would have to modify that routine Danny pointed out, so that it would implement the wanted effect in the game.

Why not just hook into the wild battle part?

.wildBattle
    ld a, (Music_WildBattle - $4000) / 3

to

.wildBattle
    call CheckLegendaryMon
    jr nc, .legendary
    ld a, MUSIC_WILD_BATTLE
    jr .playSong
.legendary
    ld a, MUSIC_FINAL_BATTLE

Instead of returning an arbitrary trainer value, just return carry if it's not legendary.

CheckLegendaryMon:
    cp ARTICUNO
    ret z
    cp ZAPDOS
    ret z
    cp MOLTRES
    ret z
    cp MEWTWO
    ret z
    scf
    ret