I bought the Wrath of the Lamb DLC, but the Cathedral isn't unlocked yet. How is this unlocked? Is it because I haven't beaten the Sheol with all the characters yet?
You don't need to beat Sheol with all of the characters to unlock the Cathedral, it's available from the beginning.
Three situations are possible here: