What's the smallest animal with hemoglobin running in its veins?
It depends how different from human hemoglobin it can be and still count as hemoglobin.  Here is a cool evolutionary tree of globins.

http://www.mhhe.com/biosci/genbio/enger/student/olc/art_quizzes/genbiomedia/0329.jpg

Here is the worlds smallest fish.  Fish have hemoglobin similar to that of humans.
from Wikipedia:  The world's smallest fish is Paedocypris progenetica1 from Indonesia, with mature females measuring 7.9 mm (0.31 in).



But I think bloodworms are even smaller. They have hemoglobin too.  It is evolutionarily more distant from us but they use it for the same reason we do.


from https://www.prestoninnovations.com/img/media/Seq-7.jpg

http://www.allaboutworms.com/the-basics-of-blood-worms


  Blood worms are red because their blood plasma contains haemoglobin,
  like human blood. Also spelled “hemoglobin,” haemoglobin increases its
  ability to take up oxygen. The larvae commonly burrow in the
  oxygen-poor mud bottom of pools and rivers, so haemoglobin is of great
  value to the larvae.


If you are going to allow very distant relatives,  I think this snail is even smaller than the smallest bloodworm.  Less than 1 mm.  Molluscs have hemoglobin too. 


from https://www.slideshare.net/fmoretzsohn/texas-seashellsmore-than-you