Community

Im working on rb heartless.

So far as must plays i feel like entomber exarch, olivia voldaren, phyrexian metamorph, bloodgift demon, inferno titan, wurmcoil engine and rune scarred demon form the back bone of the deck. 
For support i like solemn, urabask, perilous myr.

Perilous myr can trade with noble on the block as early as turn 2 and as late as turn 4, and helps the aggro match up because it allows you to follow up a t2 heartless with a free shock.
Solemn fixes mana, and give you a card when it dies.  For the rare times you stick a second heartless, its a free rampant growth that cantrips.
Urabask is a global tempo engine, allowing you to end a runescarred/metamorph chain with a lethal swing in the air, or t3 urabask, t4 inferno is entirely back breaking in most match ups.

Are there any other creatures that seem must run with heartless in red or black?

I'm playing R/B heartless online. The deck can beat any tier deck, however, the deck struggles against any deck containing blue. The backbone of the deck is Solemn, Bloodgift, Olivia, Inferno and Wurmcoil. Urabrask and Inferno can end a game in one turn but the combo is fragile and doesn't happen as often as you would like it to. I removed Urabrask for more creature hate and the deck runs smoother and is more stable.

I suggest turning the deck into u/b if you want to run the metamorph/runescarred combo. The r/b version is focused more on creature hate and burn.

Here's the list i'm playing right now: magic.tcgplayer.com/db/deck.asp?deck_id=... It's a combination of two deck designs, Niche's monoblack infect deck and Octop's R/B heartless deck that went 4-0 in a daily event.

Another explosive play with heartless is massacre wurn and falkenwrath noble. However, that combo requires more swamps.

A big explosive game changing play is the reason I play this game. I can't stand playing slow monotonous control or a deck filled with 1 drops and an average cmc of 1.5.