Yes, paging is what is necessary to run Linux. The main problem it solves is how to allocate physical memory without having to constantly move variably-sized segments around to get rid of fragmentation.
But I'm kind of sad that all OSes converged on a flat address space for the sake of ~PoRtAbIlItY~. Monocultures are bad, and we currently have one, where everything is basically a UNIX clone written in C.
32-bit x86 allowed to use both segments (of any length up to 4 GiB) and paging at the same time. Before the NX bit was introduced, this was the way to have write-xor-execute permissions. And some security features of segmentation can't be replicated at all in a flat address space: with a separate stack segment (or one with the same flat base address but a different limit), it will be impossible to add the wrong offset to a pointer to stack and get access to data that is outside of it.
IMHO, the iAPX 432 had some good ideas, and x86 should have evolved in that direction, adding a few more "extra" segment registers which code can use freely as pointers to isolated objects. Each would have two "limit" fields (for negative and positive offsets from the base), with one of these spaces used for storing pointers to other objects, which can only be manipulated through CPU microcode that guarantees memory safety.
Instead they eliminated segments completely in 64-bit mode, except for FS/GS serving as an extra offset that gets added with no limit checking whatsoever.