I always missed getting the brick, and you can't get through the catacombs without it, but if you come before the Winged Ones twice, they toss you into the catacombs, ready or not.
There's no reason to suppose that you would need a brick before going into catacombs that have brick (or stone) walls. You can try to use the skull from the catacombs in the machine, but it just breaks and the machine still kills you, so I suppose that would be your clue to get something stronger. (Just hope that you saved before getting tossed into the catacombs.)
At least after you successfully pass through the catacombs, you can still go back inside if you forgot the coins. I imagine that you could also make it all the way to the Land of the Dead without the teacup with swamp ooze in it or without the coins for Charon.