Another disadvantage is the storing of your level data.  Since you are not using tiles, your levels become a lot larger to store and display.  Plus, you also have to keep in mind the size of your enemies and player when designing them. 

Isn't it the opposite? Since one tile takes 1 bit (basically 8 tiles takes 1 byte, which is 8 times smaller than standard tilemaps). See Illusiat series for example.

It's more limited, though. Only two kind of tile can be used in such tilemap, unless you have dynamic tilemapping like Shmibs showed once or to a lesser extent like in Illusiat 12/2004 and ROL series. Basically enemies have to be stored separately.

This is from my MazeChase game and it features dynamic tilemapping:

Pretty much, it stores the tilemap as a 64x96 black and white picture. I pixel test a spot and then I pixel test the surrounding pixels. Depending on the surrounding, the tile changes. For example, pretend o is pixel off and x is pixel on. We are looking at the center:

o x o
0 x x
0 0 0

For the maze game, since the pixel above is black, I will use a tile with an opening upward and since the tile to the right is black, I use a tile that is also opening right. This way, each bit can be one of 6 tiles It makes it verrry easy to draw tilemaps and pipes and whatnot without the user having to cycle through tiles. Also, I noticed this method on my Advanced Wars 2 game (for the GBA). You can also apply this method to do multiple types of tiles as well (like mountains and trees that vary depending on the surrounding). For that, you will need more layers.

EDIT: As a note, when the program in the screenie is in map editor mode, all it is really doing is turning a pixel on or off on the map and then checking the surrounding pixels to see what changes. The method allows for easy editing and scrolling

Yeah, I used a similar method in Graviter, so that I could reduce the number of tile types and thus have more compression.