What's the value or harm of a literal belief in rebirth? Whenever I examine the concept of rebirth in Buddhism, I cannot help it but feel great skepticism.

To put it in my own clumsy words, we have many fears and one of the greatest is to cease to exist. The solution that I have found in Buddhist teachings is to outgrow that fear in particular and fear as whole, while you're at it.

In contrast to that, religions commonly introduce some concept of life after death. Which I think is a just a very comfortable delusion, self-induced to cope with this primordial fear and with the loss of loved ones. 

What strikes me is that "Buddhists" talk quite a lot about rebirth and will actually give extremely precise and concrete responses to questions on rebirth, that can quite obviously not be challenged by the examining mind. It is my (limited) understanding though at its very core (if such a thing exists) Buddhism generally denies to answer any questions that cannot actually be challenged and particularly denies to answer this question.

I feel that much is to be gained from the concept of rebirth if explored as a metaphor, but it is my impression that believing it literally is diverting attention from the here and now and more practical aspects of Buddhist practice, thus ultimately being harmful. It seems to me like failure to remove the poisoned arrow.

At the same time it makes me nervous that I cannot see any truth in more physical and concrete notions of rebirth, because it's far more likely that I am just blind, rather than everybody else being deluded. So: what is it that I am missing? What do I gain if I embrace the belief that "I" will roam this world in a new body once this one dies?
I think you're right to question the importance of rebirth; the Buddha himself didn't seem to dwell on the concept, though remembering one's past lives does have obvious practical benefits - lots more experience to draw upon :)

Bhikkhu Bodhi wrote a couple of things about the subject you might find interesting:


Dhamma Without Rebirth?
Does Rebirth Make Sense?


As he says in the first link,


  If we suspend our own predilections for the moment and instead go directly to our sources, we come upon the indisputable fact that the Buddha himself taught rebirth and taught it as a basic tenet of his teaching. Viewed in their totality, the Buddha's discourses show us that far from being a mere concession to the outlook prevalent in his time or an Asiatic cultural contrivance, the doctrine of rebirth has tremendous implications for the entire course of Dhamma practice, affecting both the aim with which the practice is taken up and the motivation with which it is followed through to completion.


I've talked about the subject before myself, and the conclusion I make is that it's not that Buddhists believe in rebirth, it's that we don't believe in death - the latter being merely a concept referring to the change from one set of experiences to another. True death only occurs either at every moment or at the experience of nibbana.

In any case, as useful as rebirth may be in reminding us of what's really at stake in our dhamma practice, far more useful is an understanding of the present moment, something that really has little to do with past or future lives.