I know they aren't the usual worshipers of Eilistraee, but is there anything realistically stopping them? I'm wanting to make a chaotic good Hellbred cleric that worships her. The backstory behind it would be that because of the character's appearance they got turned away by most good faiths, but the church of Eilistraee didn't. The redemption aspect of the faith involving the Drow is also similar to Hellbred.
They can, beware being a rebel copycat though. Consider Illmater instead. As the god of compassion, he would be rather annoyed at anyone who turned away a worshiper literally rescued by an act of grace.
As OOTS points out, the idea of the chaotic good rebelling against a evil society has become somewhat ... cliché. If you're looking for a theme of redemption and persecution, I would recommend Illmater instead. The god of compassion, his story of endurance and forgiveness fits the hellbred quite well; especially if one of his followers was directly responsible for your rescue by taking your place.
If your relationship to FR religion is important to your character, Illmater provides a much more effective foil of "should I be damned?" than does the dark maiden. It also offers an effective foil to the nominal personality of Grim McGrimson of the typical hellbred, You could even go so far as to be on a quest to show Tyr's followers the errors of their ways in judging you after redemption.
In short, nothing of the dark maiden's espoused philosophies seems to fit a hellbred cleric well, though that dichotomy could, itself, be an interesting plot point. If the primary theme that you're looking for is rejection due to superficial judgement of your race, the dark goddess of beauty is not really the best fit.
It's allowed by the rules
You can work this in even under a fairly strict reading of their racial (Fiendish Codex II, pg 77) and deity (FR: Faiths and Pantheons, pg 23) entries.
As you mentioned in the question, the redemption aspect is very similar. Specifically, Eilistraee's message of "a rightful place awaits you in the land above" seems similarly in line with a race coming from the dark of the lower planes and reaching for the light of the upper ones.
The parallels don't stop there though. Even if you felt the need to restrict a character to the alignment descriptions of their race, Hellbred are listed as having some Neutral Good and Chaotic Good members among them. Both of these alignment are among those listed for worshipers of Eilistraee. The additional text in their alignment section also fits rather well with her dogma. "Be always kind, except in battle with evil" and "Repay violence with swift violence so that those who cause it are swiftly dealt with" seem rather good fits with a race that is dedicated to the eradication of evil.
The worshiper entry is the only part that seems like it might offer problems, as the only non-elf type listed among her worshipers is "hunter". That seems a simple thing to include in a character if you were being a stickler for compliance however. I can't see a hellbred that isn't hunting evil without diverging strongly from the rest of their writeup (and which would make this deity a poor fit for other reasons).
There's nothing realistically stopping them
They fit the mechanical restrictions (if you even read those as such), and there's little stopping them from going the rest of the way. A hellbred worshiper might be a bit more arts oriented than normal for the race, as Eilistraee does promote song and dance, but these seem like concepts that could be easily worked in as character quirks.
Absolutely. There is no example of Eilistraee or her followers rejecting anyone based on their race. Not every Eilistraeen group is the same so some may be more open than others. However generally speaking you may expect to be the target of many discern/detect lies spells or even a few circles of truth early on. But as long as you are found to be honest you will be quite welcome among the followers of Eilistraee.