If I have a table where the data is guaranteed to never change, is it completely safe to add the NOLOCK hint to my SELECT queries against that table?
In practice, yes (although not documented as such), but also useless. If your data never changes, then using dirty reads won't cause any observable behavior or material performance difference.
If I have a table where some of the rows will be updated, but I'm only selecting rows that are guaranteed not to change, is this also a completely safe scenario to use the NOLOCK hint?
No. Absolutely not. The query plan to read the target rows may read changing data structures without proper concurrency controls. So you are back to hoping that your queries don't return bizarre, incorrect results or simply fail.
Is there any (even negligible) performance differences in using the NOLOCK hint in the first scenario? Also, in the second scenario when you say "changing data structures", are you referring to the underlying pages that the data is stored on (because it can be sharing a page with rows that are changing)?
In the first scenario you might see some cost for row locking if you're not using READ COMMITTED SNAPSHOT (with some mitigation due to unchanging data). But using TABLOCK instead of NOLOCK in that scenario would force a single S lock for the query. TABLOCK enables allocation-order scans just like NOLOCK, but without dirty reads.
The "changing data structures" might include the data pages and indexes. The lack of coordination between data page reads and index reads is a main cause of NOLOCK badness.