Secondo W3C ( http://www.w3schools.com/tags/tag_noscript.asp )
il tag noscript serve SOLO per contenere "testo alternativo " allo script, quindi se ne intuisce una funzione di "avviso ".
Con questo preambolo è ovvio che, il noscipt, deve trovarsi nella posizione il cui script non può agire. Ecco che qui la tua domanda prende maggior enfasi : "Se in HEAD ho uno script fondamentale per la navigazione, come posso dare un'alternativa?"

Sebbene la questione da te esposta (ad esempio inviare l'utente su un CSS differente) sia argomento davvero valido, pare non ci sia soluzione; a parte l'interessante esempio da te proposto, purtroppo macchinoso. Se poi la cosa si riesce a semplificare... meglio!
Anzi: avvisaci!

La legge Stanca sappiamo che parla della reale accessibilità, e non di cosa si scrive nel codice.
Non parlo per esperienza diretta... ma credo che se una cosa funziona ma non è validata, all'utente non importi molto. Quello che conta, per certi utenti , è poter usare lo strumento.

Del resto "Accessibile" e "Validato" non sono proprio la stessa cosa.
Rimane "aperta" la questione di dare un riferimento univoco al browser per l'interpretazione del codice.

La mia è solo una riflessione: NON è un invito a non validare !