Card choices:

– Rihad Horseman – this card is a beast. He can often win the game all by himself. Protect him at all cost.
– Lesser Ward – not a very splashy card and it can actually be easily replaced, but they are here to protect your heavy hitters like the Horsemen and Graystone Ravager.
– Niben Bay Cuthroat – probably the weakest card in the deck, as it will almost always be a 1/1 but it can be used as a good fodder for Soul Split. Also, with so much removal, you can easily clean the lane and trigger her ability to deal an additional 2 damage to the face.
– Ice spike – more damage to the face and card draw. Use it when you are running out of steam or you have nothing else to play.
– Soul Split – I originally played with three of these, but I soon discovered that I often didn’t want to sacrifice my buffed-up creatures just to summon two 3/2, so I cut them to two, and then finally to one. It can be used as an extra push for more damage, triggering your last gasp guys in the process.
– Morkul Gatekeeper – nice guard to keep your Horsemen alive. Choosing who to target with its ability can be tricky. I usually avoid targeting himself but instead target another creature to deal even more damage to the face.
– Lightning Bolt – this card can help you seal the deal. If you see it in your opening hand, mulligan it! We want these to trigger from prophecies.

How to play:

Basically, go to face. Don’t be greedy with your equipment and don’t place anything on one creature (unless you are about to deal the death blow). Try to use it on guys like Rihad Horseman and Rihad Battlemage, especially the former as it can easily grow out of proportion.
Actually, try to keep all your equipment for late game to quickly finish the game with one or two hits. Also, don’t use your Nord Firebrands until late in the game. With equipment like Steel Sword, you can equip them the turn you play them and they can become like a mini Lightning Bolt. Speaking of Lightining Bolt, use it to deal those last few damage to the face, but don’t be afraid to use it to remove some annoying creature on the board like Quin’rawl Burglar or Moonlight Werebat. Ditto for Crushing Blow.
Don’t use Rapid Shot to kill, unless is some really annoying creature or to remove guards. Card draw is much more important than 1 damage. Remember that you can also use it on your own creatures in desperate situations, like when you really need that Steel Sword from Dunber Nightblade or that 3 random damage from Ashlander.

Conclusion

So there you go. An all-common deck is very much possible, to my surprise. It is also a very fun and easy deck to play, not to mention SUPER cheap! Destroying other people super expensive legendary cards with this deck never gets old.
Of course, nobody is forcing you to use all-common cards, so there is plenty room for improvement and customization. I would love to hear your thoughts and comments! Have fun!