According to this Skanda Purana chapter the leaves can be offered to Lord Shiva. The Shiva Lingam called Arunachala is in fact prescribed to be worshipped with Tulasi leaves.
This Arunachal is expected to be Parameswar Himself and a fourteen
kilometre distance surrounding the Mountain is as good as a complete
‘Pradakshina’ (Circumambulation) of Lord Siva. A large number of
persons perform the Pradakshina on every full moon night barefooted
and Pournami of Chaitra Month is a very special day as over hundreds
of thousands throng the Temple and the Mountain displaying sincere
devotion from all over the World. A ten day long celebration
culminating on the day of Karthika Deepam or lights day is a massive
crowd puller; on that evening a huge lamp is lit in an open vessel
with three tons of ghee from the mountain top. Among the ‘Pancha
Bhutas’ (Five Elements), viz. Earth, Water, Fire, Wind and Sky, the
Fire is the symbol of Arunachaleswar as a corollary of the Agni Stumbh
referred to as above.(The ‘Tiruvannaikavil’/ ‘Jalakantheswara’ Linga
represents Water, Kancheepuram / Ekambareswara Linga the Earth,
Kalahasti represents Vayu and Chidambaram represents Akash or Sky).
Nandikeswar told Markandeya that at the commencement of ‘Ayanas’
(Fortnights) or Vishuvyog times, worship to Arunachal Linga would be
very propitious. Early morning puja is performed with ‘Tulasi’ leaves,
the mid-day puja with ‘Amalataasa’ and Bel flowers in the evening. By
chanting the ‘Aghora Mantra’viz. Aghorebhyothaghorebhyo Namasthey
So, apparently not prohibited but usually no one does that too.
UPDATE:
Upadating the answer from ShAktAnanda Tarangini's (overview of the text is here) 14th chapter:
Tulasi leaves are said to be indispensable for many sacred rites as said below (the verse is from YAmala Tantra, all the verses are from that source too):
VinA tulasyA snAnAdi shrAddham yajnamcha na priye |
O Beloved! Without Tulasi no rites like holy bath, Homas or ancestral
rites can be successfully performed.
But for some deities it is forbidden to be used. For example for Goddess ChandikA:
Tulasi AghrAnamatrena kruddha bhavati chandikA |
It says that Goddess becomes angry even by the smell of Tulasi.
Similarly for Lord Ganesha and other deities:
Sarvadevamayi sA tu ganeshasya priyA na hi |
LakshmidevyAshchApriyA hi tArAdevyAstathaiva cha||
This verse says that although Tulasi is "Sarva Devamayi" but it is not liked by Lord Ganesha. It is also not liked by Goddesses Lakshmi and TArA.
So, point is, among all the deities, for whom Tulasi is forbidden to be used during worship, Lord Shiva is not mentioned.
Therefore, we can assume, that it is not forbidden but since it is not a favorite of Lord Shiva, usually no one offers it either.
For the restricted flowers in Lord Shiva's worship the same YAmala has the following verse:
Vakulam mAlatim jAtim kundam shephAlikAm jabAm |
Na dadyAccha
mahAdeve yadicchechubhamAtmanah ||
One who desires one's own good must not offer MahAdeva the following
flowers- Vakula, MAlati, JAti, Kunda, ShephAlikA and JabA.
So, apart from Ketaki flowers, these are the other forbidden flowers not to be used in Lord Shiva's worship. Since, again, Tulasi is not mentioned we can assume that it is not prohibited.
NOTE: Will check Nityotsava too and will update the answer further if something relevant found in it.