How to override "Who's online" block theme without any change to "Who's new" theme
Since they both use the same theme function it gets more complicated.

The only real choice you have to alter the markup of the one block, but not the other, is to template_preprocess_block or templates for the blocks. The problem is that by this point the markup for the actual block content has already been created, which means that you would either have to recreate the markup, or use some pattern matching to alter the created markup. Both of which is not really desirable.

Another option would be to create the block yourself like the user module does but alter the markup that is created.