noframes, da würde ich persönlich dann auf die im frameset eingebundenen seiten verweisen, mit beschreibung, so á la "hier ist die navigation und dort ist die index-seite". das ist zwar unbequem, aber noch handlebar...
und für die, die kein js anhaben, setzt du einfach den <noscript>-tag und bastelst da eine html-variante rein.