It is not mentioned in _Fantastic Beasts and Where to Find Them_ whether or not the basilisk is resistant to spells.

I would imagine Avada Kedavra would kill a basilisk; the difficulty is in casting the spell without dying yourself. If it went hunting in the castle, the basilisk had a much better chance of killing as it had the element of surprise.

The support for my speculation comes from the fact that basilisks must have been killed before. I doubt every wizard happened to be able to stab it through the head. However you can also take it as another way as we only have two canon examples of basilisks:

* Salazar Slytherin's which was killed by a sword to the head 
* Herpo the Foul's, about which all that we know is that it died at around the age of 900 or for quotes sake: 
> Herpo the Foul's Basilisk is believed to have lived for close on nine hundred years.

All we know for certain is that Basilisks were created and were killed. We do not know by what means but one can theorize spells had to be used at some point, so it stands by that logic that a banned extremely powerful spell could have been used.