The Bloody Palace mode is unlocked after you beat the game on any difficulty. It is a gauntlet-styled mode where you must fight of a waves of enemies to proceed. Each wave's enemies will vary, and every 10th wave you will face a boss. As your progress though the different floors, enemies will get tougher and tougher.
When you beat a wave you will be offered 3 different portals:
A water portal that will take you up one level but give you health.
A lighting portal that will take you up ten levels but give you Demon trigger magic.
And a fire portal that will take you up one hundred levels but give you no health or DT magic.
In order to get through all 9999 levels you're going to want to use the fire portal unless you absolutely need more health. This means 101 waves of enemies with no health or devil trigger regeneration outside of what you earn in combat. Items and saving also aren't allowed in this mode, but it's still possible.
The keys to the Bloody Palace are the super characters and full upgrades.
Super Dante or Super Sparda still don't make this easy, but they make it substantially easier. You don't have to worry about devil trigger, because you have infinite devil trigger. You can also regenerate a little bit of health if you work devil trigger right. However, to unlock a super character you have to beat the game on Dante Must Die mode. Refer to Hell Hath No Fury... for more details.
You'll also want to have fully upgraded styles, devil arms, guns, and health for this. It's 101 waves of enemies and ten bosses. The orb grind is worth it if it saves you from having to repeat this. For more details on upgrading and maxing out your health, refer to these achievements:
Left No Stone Unturned
Maximize Your Health
Even with a fully upgraded super character, this will be still challenging and will take about two hours to do. By completing Dante Must Die difficulty, you should have learned what works against what enemies, so utilize that skill as much as possible.