Your first option is the good one. It's the least problematic one and you've already found the correct reasons why you couldn't use the other options.
By the way, your heading IS explicitly associated with the <ul>
: it's right before the list! ;)
edit: Steve Faulkner, one of the editors of W3C HTML5 and 5.1 has sketched out a definition of an lt
element. That's an unofficial draft that he'll discuss for HTML 5.2, nothing more yet.