As for freeze mage, it needs very specific expensive cards for it to have any effect, and imo its not the greatest deck to focus on as your main (its risky depending on meta, some matchups just crush it).
First of all, you should disenchant your Kidnapper (rogue epic), its useless for its cost and unless blizzard changes it (pretty much impossible), it wont see any play.
As for decks, its still too early to think of anything worthwhile. You have some good cards here and there but these are just single copies. By the looks of it, you could try Shaman with Sea Giant, Lighting Storm, Feral Spirits, double Stormforged Axes, Earthshock, double Rockbiter Weapon, Crackle, double Flametounge Totem, double Hex, Unbound Elemental, double Fire Elemental, Earth Elemental, Piloted Shredder, Azure Drake, double Sen'jin, Chillwind Yeti, double Argent Squire, Antique Healbot, Loot Hoader, Stormwind Champion and double Frostwolf Warlord for funz. I know you didnt want a full deck, but you could give it a try.
Your priest doesnt have too many cards, but double Thoughtsteal would definitely deliver you some fun games (best card in the game). With so many cards you would have to put as many board control spells into your deck, like all Shadow Words, double Holy Nova, double Mind Control, Clerics as your card draw engine, PW: Shield, maybe Smites, Temple Enforcers, MC Tech for more control and Injured Blademaster - its great in priest. More below.
Other than that, as i said its too early to think of any big combos. Good allround cards you could fit into any deck are: 1 copy of Acidic Swamp Ooze, Loot Hoader, Mind Control Tech if you face a lot of spammy decks, Scarlet Crusader is nice in some cheap decks, Shattered Sun Cleric if you dont have too many 3-drops in your deck, Tinkertown Technician if you run some mechs in your deck, Chillwind Yeti, Piloted Shredder is great, Sen'jin if you need taunts, Antique Healbot if you have problems with your health dropping too quickly, Azure Drake is great in conjuction with damaging spells, preferably AoE, Argent Commander for something rushy. Other great non-basic class-cards you have are Shielded Minibot and Aldor in Paladin, Thoughtsteal and Auchenai in Priest, and Imp-losion in Warlock.