Dude, you basically set up an entire generation's worth of ideas. Hell, your list actually illustrate just how much potential has gone untapped on part of the Pokemon designers.
I was actually doing something similar myself the other day, including making my own list of possible type combos. Guess I'll just post my ideas now.
Normal/Ground = Gopher Pokemon. Maybe a two stage evolution.
Normal/Bug = Worker ant Pokemon.
Normal/Ghost = Skeleton Pokemon. Could evolve from a disembodied skull head.
Normal/Ice = Polar bear Pokemon. This one's been done already.
Fighting/Flying = Hawk Pokemon. They're birds of prey you know.
Fighting/Bug = Scorpion Pokemon. I think this type combo's been done already though.
Fighting/Rock = Stone statue Pokemon. Like a real golem.
Fighting/Ghost = Boxing ghost thingie. Something like Biff Atlas or those Boos with the boxing gloves from NSMB.
Fighting/Steel = Robot Pokemon. Not like Magnemite. I mean something like a B-movie robot or a Gundam.
Fighting/Electric = Something similar to Electabuzz. Hell, I', surprised he wasn't fighting/electric already.
Flying/Poison = Hummingbird Pokemon. I think this type's been done too.
Flying/Ghost = A Pokemon that looks like a little flying demon thing. We need more demon Pokemon. ;D
Poison/Rock = Sludge covered boulder Pokemon. Either that or an alternate evolution for Koffing I called "Sneezing".
Poison/Fire = Smog cloud Pokemon. Like Mokura from SMRPG. Either that or a flaming snake Pokemon.
Ground/Bug = Sandcrab Pokemon.
Ground/Ghost = Zombie Pokemon. They could start out as an undead hand and evolve from there.
Ground/Steel = Ore Pokemon. Actually, I think this one may have been done already.
Ground/Grass = Tree stump Pokemon.
Ground/Electric = A Pokemon that looks like a cross between Pikachu and Sandshrew.
Ground/Dragon = Some type of giant sand serpent, like the desert boss in ALttP.
Rock/Ghost = A possessed Tiki idol Pokemon.
Rock/Grass = A boulder Pokemon with moss or vines on it
Rock/Electric = An electrified boulder Pokemon, like the Stone + Spark combo from Kirby 64. Yeah, my rock-type ideas suck.
Rock/Ice = Either a chunk of ice or an icicle Pokemon.
Rock/Dragon = A dragon statue Pokemon. Simple enough.
Bug/Fire = Firefly Pokemon.
Bug/Water = A water skimmer Pokemon.
Bug/Electric = Either a lightning bug or glow worm Pokemon.
Bug/Dragon = Either a dragonfly (which was already done, dammit) or a dragon with bug wings (like Dogadon from DK64) Pokemon.
Ghost/Steel = Floating sword Pokemon. It could evolve into a full suit of armor. ;D
Ghost/Fire = Will O' the Wisp Pokemon.
Ghost/Water =I'm not sure, but it should be piratey. Maybe a Kraken Pokemon?
Ghost/Grass = Jack o' lantern Pokemon. This one's been done already.
Ghost/Electric = A Pokemon that resembles Plasma Wisp from Kirby or Sparky from Mario.
Ghost/Ice = A Pokemon like that ice guy from that one episode of Aladdin. What the hell was he called again?
Steel/Fire = Either a train Pokemon or one based on another piece of machinery, like a car or bike Pokemon.
Fire/Water = Steam Pokemon.
Fire/Grass = Burning tree Pokemon.
Fire/Electric = A Pokemon that looks like Kremzeek from Transformers.
Fire/Psychic = Fire imp Pokemon.
Fire/Ice = a twin headed monster Pokemon with fire and ice breath, respectively. Possible legendary.
Fire/Dragon = A regular dragon. Why hasn't this been done yet?
Water/Psychic = Mermaid Pokemon. Yes, the type combo's been done already, I know.
Grass/Electric = Glowing mushroom Pokemon. I came up with two possible names: Gloshroom and Funglow.
Grass/Psychic = Willow tree Pokemon. Think the type's been done already though.
Grass/Ice = Crystallized/frozen flower Pokemon.
Grass/Dragon = Chinese-style dragon Pokemon.
Electric/Psychic = Lightning imp Pokemon. Counterpart to the fire imp mentioned above.