Okay, so we all probably know that there is a planed dimension called Sky Lands. It is like the opposite of the nether.
I got an idea.
In the Nether, there would be randomly generated Spawn rooms underground. Maybe 5 per world or something.The spawn rooms are bright rooms. They have redstone torches. There shall be a spawner. Not a normal one. A diffrent kind. One with a thingy that looks like the end portal or something. It is sorrounded by aura that blocks any blocks from being placed in its ranged so you can't place blocks to suffocate it or anything. You place an item, maybe a magma cream, in the holes. Like the stronghold, there will be spawner frame blocks, and there will be holes in the blocks. Just like the the end portal where you use eye of ender, you use magma cream to fix the spawner. And it shall spawn herobrine. When killed, herobrine drops 5-10 of a rare item. It should be something not as rare as a Golden apple. Maybe cocobean?
Anyways, as for notch, its the same thing except in the sky lands and Notch drops golden apples. Plus, it can't be underground cause sky land floats so maybe somewhere else.
The reason for this is because in multiplayer, notch drops red apples but for something hard to find, it should drop better stuff like golden ones.
If you think magma cream is too easy, well think again. There is no way to find the spawn rooms without mining underground. And seriously, unless you want tons of netherrack, no one will mine there. Plus, its rare.