Good question.

Like other posters have pointed out, the source of that metallic smell when you rub coins is actually the oils on your hand. Specific metals catalyze a lipid reduction reaction, then you smell the reduced, decomposed lipids and recognize it as that metallic smell.

The actual metallic taste in blood is unknown -- you have a certain quantity of free metals dissolved into your blood, among them are copper, zinc, and iron, but the actual source is debatable. There is some data suggesting that when certain iron compounds such as ferrous sulfate are ingested, some of the "taste" is actually a smell coming from within the mouth (retronasal smell: smell passing through the back of your mouth and onto your olfactory nerves), and it has been hypothesized that it's that same lipid reduction as seen on your hands. However, other metallic compounds such as copper sulfate and zinc sulfate can be tasted without any retronasal smell.

So, we still don't know what the taste actually is, but we have some idea.

And, just for completeness: the iron in your body is not all bound up in hemoglobin. In fact, most of it is bound to a storage protein in your intestines called ferritin while quite a bit is in equilibrium with a transportation protein in your blood called transferrin. When it isn't being actively stored or transported, free iron will accumulate in your tissues (get enough and you might kill yourself by hemochromatosis). But the basic point is that iron is certainly moving around in your blood independent of hemoglobin.