As i've completed a couple of 500th level runs i thought i should add to this.
Level 30 is about the average level you should be looking at to be able to get to level 500. It does depend on class, skills and meat, and will probably be a bit more for newer players (though i would recommend they get a few ascensions under their belt before trying this), and less perhaps for older players, with a lot of meat to spend, but my two level 500 runs have finished as Level 32 Sauceror (i could have completed it quicker than that, but that was my first time in the basement), and level 30 Turtle Tamer.
The key for everything really is Reagent Potions, which is why Sauceror is a must for every players first run, as you can cook three Reagent Potions for the ingredients of one. That combined with the 80%/90% (can't remember which) max elemental resistance from the Sauceror class means you will find many things far easier. Reagent Potions can be used for stat boosts, for the elemental challenges (the phials, which also double up as a way to defeat the enemies with physical resistance). So if you are on a budget, go with Sauceror (or at least do a Sauceror lead in run, where you can prepare yourself plenty of potions for the basement). Elemental challenges don't need semi-rares, as you can boost up enough with items, so you can max out your HP with equipment instead.
For the combats, i'll repeat what everyone else has said, the divine combat items are brilliant. Combined with funkslinging, and you should not have a problem with anything in the basement if you are at a good level.
MP tests is where i had the most problems. People forget sometimes Jumbo Dr. Lucifers restore all MP (for 1 fullness), so are brilliant if you are on a budget to restore your MP. Don't think about going for MP boosting items though, it is (i think) better just to focus on Myst boosts. I don't see how anyone could try for the basement without Wisdom of the Elder Tortoises, given how frustrating (even as a sauceror) the MP tests are.
Finally, Roasted Marshmallows. These are something that need to be considered carefully. I think they may turn out to be very useful, if you use them right (remember the max percentage increase with them is 500%). Saving your fullness till the end of the day, then eating them, getting drunk, going past rollover, and eating 15 more gets you 90 turns of the effect (starting off at 450% boost), is the most efficient way of consuming them, but they are only (i would suggest) useful for late on, if you are trying at a lower level to get down to 500 (or even stacking the effect into a third day, getting it to 500%, and eating a marshmallow every 3 adventures to keep the strength of the effect while basementing works well, but is fairly costly, and is not that efficient with adventures).
