Fiendish Codex I has complete demonic possession rules, and doesn't say anything about minimum HD, iirc. Incredibly good stuff, too!
As for the OP's question, how about planar binding a fiend and working out a very specific contract? Make sure to have an exorcist stand by, though...