You were playing Pokemon Red or Blue, and this is known as the Missingno glitch. This glitch is rather interesting, so I'll include some details on how it works.
Essentially, there was an oversight in the code that made the right edge of Cinnibar Island (where there's the black-ish border) have some unique properties. It counts as a zone where wild Pokemon can spawn, but it also does not specify which Pokemon should spawn there. Because of this, it always uses the Pokemon that were in the last zone that you visited. Thus, it's useful for catching rare Safari Zone Pokemon, because you can battle them for real, putting them to sleep and damaging them, rather than relying on the luck of the Safari Ball.
But that's not enough to explain how Missingno came about. There's more to it. Here's where talking to the Weedle Man comes into play.
When you talk to the man in Viridian City who teaches you how to catch Pokemon by demonstrating on a Weedle, there are some interesting things done with the game's memory state. Pokemon uses all the memory available on the old Game Boy cartridges already. But at this point in the game, it wants the player's name to show as "OLD MAN" rather than whatever the player chose.
In order to do this, it must copy the player's name to an unused portion of memory. Namely: The area where the Pokemon spawn rates for the current zone are stored. Usually this hardly matters, because when you enter a new zone, those values will be overwritten by the ones for the new zone. But if you go straight to Cinnibar Island and ride up and down the coast, some weird things start happening.
Since it doesn't reset which wild Pokemon can spawn, and the last thing in that area of memory was your character's name, not a real spawn table, there are a whole variety of possible outcomes. Pokemon spawn higher than level 100. The Pokemon that spawn are random, depending on the characters in the player's name. And Missingno appears, when there is no real Pokemon corresponding to the data in the table.