否定の文字クラス使えば、普通に最短マッチで出来る事だろ。
s{<li>([^>]*?</li>¥s+</ul>)}{<li class="a">$1}sg

パースするライブラリ使えっつーのは同意だがな