How I would handle it:
I'd use two optional rules, one of which would be tweaked. One would be
bloodlines, with the other being
reducing level adjustments.
Rather than using the Bloodlines as-written, I'd use them but call them
inherited templates with a +LA value equal to the number of levels the bloodline consumes. This allows PCs to buy off the LA of the templates, rather than get stuck with nigh-empty "bloodline levels." This seems to fit well with the Bhaalspawn in the games, which did not lose levels at any point, while still making an attempt at balance (through xp expenditures).
Bloodlines of Murder
First, I'd determine the Bhaalspawn strength. If the PCs are aware of their heritage, I'd allow them to choose the bloodline strength on their own. If not, I'd select it for story purposes, or roll it up randomly.
Table B-1: Bhaalspawn Bloodline Strength
% Roll* - Strength
1-25 - Minor
26-75 - Intermediate
76-100 - Major
* A character of an evil alignment gets a +5 bonus on this roll.
Then, I'd determine what type of bloodline to use, based on the PC's Alignment. This wouldn't be set in stone. If the PC changed from one alignment to another in-play, then they'd retain their previous abilities and powers, but I would "switch over" the bloodline from that point onward:
Table B-2: Bhaalspawn Bloodline by Alignment
Character Alignment - Bloodline
Lawful Evil -
Devil
Any Good -
Celestial
All other Alignments -
Demon
Consider using dream sequences like in the games to represent the call of the Bhaalspawn power within the character. If Good characters don't reject the demands of Bhaal within them, they get the evil powers rather than the good powers for their next level.