Short Version:
Shinigami bleed because they have blood. Thanks to science-minded characters like Captain Mayuri Kurotsuchi and Szayelaporro Grantz and their talk of organs and nerves, we know that a shinigami's body has these components and functions very much like a living human's body. Thus, we can infer they also have blood vessels and blood.
Long Version:
The question of what sort of substance a soul is made up of is one that many philosophers have taken on through the ages. A follow-up question would be how this substance interacts with other substances. Bleach seems to give partial answers to these questions for the universe in which it exists.
So, in Bleach, there are two substances: The substance that makes up a living human body (physical matter), and the substance that makes up a Shinigami and Wholes (Reishi). As it turns out, in the world of Bleach these substances are very similar. Living humans and spirits both have organs and bleed. Though there is some uncertainty with how physical matter and reishi interact, at least when separate in their own worlds (the World of the Living and the Soul Society) they behave in similar manners.
In western culture, we tend to view spirits and the afterlife in a very ethereal way. The substance of the soul and the body are considered to be very different. This is probably why it seems so strange in Bleach that ghosts can bleed. The idea of a more physical afterlife was not unknown in the ancient world, though, and can be seen in the Norse Valhalla, where fallen men eat, drink, and do battle. Also, many Christian denominations believe that Jesus ascended to heaven with his physical body and that there will be a physical resurrection of the body at the end of times.
Also relevant: https://en.wikipedia.org/wiki/Resurrection and https://en.wikipedia.org/wiki/Transcendence_(religion)