Here's some development art I found.  

http://archives.bulbagarden.net/media/upload/7/70/Pokemon_conceptart_big.jpg

It was supposed to have a Final-Fantasy overworld, and all the Pokemon appear in this picture have low index numbers (Which are the same as the numbers you use for gameshark codes relating to Pokemon), or either don't appear at all.  I even heard once that indeed Rhydon was the first Pokemon created (With it's index number being 01).  So from what I understand, the list you're seeing on several gameshark sites listing Pokemon by their index number, not their Pokedex number, is basically a list of when Pokemon were created, Rhydon being first, Victreebell being last.

I have hacked Pokemon Red to death (Literally, check my hack Pokemon Brown /useless plug), and from what I can tell, Missingno's were Pokemon that were deleted before the final release.  Either Pokemon that would appear in later generations, or Pokemon that have still never seen the light of day.

One interesting quality of the Missingno's is one Missingno has the exact same cry as Crobat, which leads me to believe Crobat was meant for the first generation instead of the second.

On another note, I respect the programmers at Gamefreak, but when looking at the code he wrote in the Pokemon Red ROM, I simply cannot understand what the hell they was thinking.  Everything is so disorganized and programmed in ways that no other games have used.   Here is a sample of this nightmare:

Hidden items, in Gold its programmed like this in the map's events: declaration that this even is a hidden item, Y, X, Flag Number, Item. Very simple.  

But no, in Pokemon Red, there are several lists to make this work.  First is a list of all the maps that have hidden items, followed by a pointer table. The pointer table reads from the first list so it knows which map to place to items on.  So you follow a pointer, it has an Y, X, and item number, followed by a pointer which links to the hidden item ASM.  You think it's over, but there is ANOTHER list at the end of the ROM.  Map number, Y, X, repeated, basically the same exact data from the previous table.  These declare flags in the RAM (So you can't pick it up twice).  Declaration 1 is flag 1, declaration 2 is flag 2, but I don't understand why they had to put the same data twice instead of just having it read from the previous table.  That's just one of the many examples...

On the bright side, Pokemon Gold's programming is a vast improvement over Reds, is very organized and things actually make sense.