Re: yor question; the homologies between monomeric globins like myoglobin and oligomeric hemoglobins are well established. We don't know what the ultimate ancestry of the globin gene is (it's likely older than a billion years) but we can construct perfectly good phylogenies for the multicellular organism globins. If you accept a phylogenetic tree as evidence for evolution, and we do, then there are no miracles necessary to evolve hemoglobin from monomeric proteins. Where the ancestral globin gene came from is still a mystery.
Some refs.
http://allserv.rug.ac.be/~jvfleter/globins/globins.html
http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?cmd=Retrieve&db=PubMed&list_uids=8587498&dopt=Abstract
http://www.aw-bc.com/mathews/ch07/fi7p23.htm
I had meant to type in (emphasized text added), but of course got sidetracked and then just cut and pasted (emphasis added) from the prior quote.
Thanks for the references.