In ray tracing, there are three commonly used spatial acceleration structures these days: grids, binary space partitions, and bounding volume hierarchies. Any one of those might have worked for Doom.
Though this post mentions marching through grids (as in Wolfenstein 3D) as not working for the arbitrarily positioned and angled walls, the usual way of using grids for ray tracing is to have each grid cell hold a list of the primitives that overlap it (many-to-many). Then you march the ray through the grid and test the ray against the list of primitives for each cell. You'd often use "mailboxing" (i.e., tiny LRU) to prevent retesting the same primitives over and over, since adjacent grid cells would often share primitives.
So basically extending the Wolfenstein 3D grid approach to Doom would have mean voxelizing the map to get lists of candidate walls for each cell, but testing the rays against the walls themselves (rather than say, the voxels themselves like in Minecraft).
I'm not sure what the tradeoffs for memory or performance on the 386s of the time would have been, however. But I think it's clear that while BSPs were a clever solution, they weren't the only possible choice.