Why do we need red blood cells?
Hemoglobin molecules used to manufacture these products are not
  contained by a red cell membrane, and when released into the
  vasculature, these molecules rapidly scavenge nitric oxide.This can
  result in systemic vasoconstriction, decreased blood flow, increased
  release of proinflammatory mediators and potent vasoconstrictors, and
  a loss of platelet inactivation,17- 20 creating conditions that may
  lead to vascular thrombosis of the heart or other organs. This
  mechanism has recently been shown in preclinical models to be
  responsible for injury during hemolytic states, in which hemoglobin is
  also released into the circulation.21
  
  Unlike naturally occurring hemoglobin, manufactured cell-free
  hemoglobin-based blood substitutes (HBBSs) can be chemically altered
  to theoretically minimize such toxicities. It has been postulated that
  cross-linking, polymerization, or pegylation of hemoglobin will create
  larger, more stable HBBS molecules, preventing extravasation and
  thereby leading to a reduction in toxicities related to nitric oxide
  scavenging. At least 1 manufacturer has also chemically increased the
  affinity of its HBBS for oxygen (lower P50, the partial pressure of
  oxygen required for 50% hemoglobin saturation) to decrease arteriole
  oxygen transfer and thereby potentially eliminate untoward
  cardiovascular effects.



2008 - Cell-Free Hemoglobin-Based Blood Substitutes and Risk of Myocardial Infarction and Death


So cell free hemoglobin is toxic. As you can see this toxicity can be reduced in other ways too, so it seems like there is an evolutionary pressure in the direction of having blood cells, maybe it is simpler this way. To answer the other question, I think there can be free HGB in the blood when blood cells fall apart because of an infection e.g. malaria, etc...


  Hemolysis in falciparum malaria results in NO quenching by cell-free
  hemoglobin, and may exacerbate endothelial dysfunction, adhesion
  receptor expression and impaired tissue perfusion. Treatments that
  increase NO bioavailability may have potential as adjunctive therapies
  in SM



2008 - Relationship of Cell-Free Hemoglobin to Impaired Endothelial Nitric Oxide Bioavailability and Perfusion in Severe Falciparum Malaria 


Btw. I agree with rhill45, I think too that it is easier to regulate O2 and CO2 exchange if you have a specialized cell type, so it might have regulation purposes. It can have recycling purposes either, because it is hard to distinguish between old (damaged) and new HGB when they are in a cell-free form. This problem probably can be solved by destroying only glycosylated hemoglobin, but I guess it is much easier to filter out the old RBCs in the spleen...


  In the process of maturation, a basophilic pronormoblast is converted
  from a cell with a large nucleus and a volume of 900 fL to an
  enucleated disc with a volume of 95 fL. By the reticulocyte stage, the
  cell has extruded its nucleus, but is still capable of producing
  hemoglobin.



according to wikipedia (without citation).


Other sources claim the same, with the extension that this period lasts only for a short time, because the cell soon loses its mRNA and so it stops producing HGB. So according to these articles RBCs create the HGBs in the early stages of their life. (I did not find a real scientific article about this, but I can accept this theory.)

According to Chris this toxicity is just a protection mechanism, so I dug deeper.


  Bacterial virulence is greatly enhanced by freely available iron, such
  as that in fully-saturated transferrin or free haemoglobin. Following
  trauma a fall in tissue Eh and pH due to ischaemia, plus the reducing
  powers of bacteria, can make iron in transferrin freely available and
  abolish the bactericidal properties of tissue fluids with disastrous
  results for the host. Hyperbaric oxygen is a possible therapeutic
  measure that could restore normal bactericidal systems in infected
  tissues by raising the Eh and pH.



2006 - Iron and infection: the heart of the matter



  Iron lies at the center of a battle for nutritional resource between
  higher organisms and their microbial pathogens. The iron status of the
  human host affects the pathogenicity of numerous infections including
  malaria, HIV-1, and tuberculosis.



2012 - Hepcidin and the Iron-Infection Axis


So RBCs protect the iron against microbial pathogens, that's their key role. I think every other related problem, like O2 release regulation, free HGB toxicity, HGB recycling, etc... can be solved with free HGB as well, so most probably iron protection is the evolutionary pressure to store HGB in blood cells instead of letting it be in the blood in a cell free form. It's funny that every single book gets this wrong, and they claim that carrying oxygen is the most important role of this cell type, while they aren't mention anything about iron protection... :-)