Since the basement floods sometimes, I'd use cinder block legs. Leave a 49" space between each leg so that later something may fit in that space. Because the floor is not level, I'd bed each cinder block in mortar, bringing them closer to level with each course of block by adjusting the thickness of the mortar joint beteen each sucessive block. If a permanent bond to the floor is not wanted, either rub the floor where the mortar bed will be with a paraffin block or set a square of wax paper there. For the shelf I would use 2 by 6's, 1/2" plywood cut into 5" strips by 8', and 2 by 4's. Stagger the board ends so they don't match, or where they must, meet centered over a block leg. Attach the plywood strips to the 2 by 6's so that there is a half inch gap at the top edge. Attach the 2 by 4's to the plywood strips flush with the top of the strip. Drop in plywood panels for a shelf surface into the recess between the rails you've created. Block the plywood joints from underneath with 2 by 4 pieces. Paint everything that is wood, all surfaces.