As I posted on this question, my roomy and I have a pretty similar problem. Our solution does require poking holes in the wall (8 I believe for our bikes) with drywall screws, but this is easily fixed with some white wood putty (from Home Depot or similar) when you're ready to move out. Because we both ride year-round (including snow and rain days), we also lined the wall and floor with plastic to keep the dripping encased. We now have 6 bikes (5 on the wall and a big-dummy under the breakfast bar), and have no indications of any problems after about a year.
It is basically a 2x4 screwed to the wall, with hooks placed into it at a 45 degree angle. Basically the wheel at the top is in contact with both the hook and the wall, and the bottom wheel is touching the wall. Alternating hanging the bikes by the front and rear wheel means you can put the hooks closer together, and put more in the same space. It is a very strong design, able to hold a couple of 40+ lbs bikes (Pugsley) and 3 other bikes.
The size of hooks may vary. For example, I have a large one for my Pugsley:
The plastic we used is also very cheap. I think it was ~15$ for 100 feet of the stuff. We plan to replace the plastic once it gets dirty, and I estimate the sheet we have will last 4-5 years. We also used patches of duck-tape where the tires hit the plastic in order to prevent the tires from wearing through too quickly (especially important for the bikes with studded tires).
The most expensive part of the build was the hooks, the most expensive of which were ~15$ (going from memory). I'd estimate the whole build can be done for ~100$ for 5 bikes.
