Can I install the native Android OS on a non-Google phone? Samsung makes up 90% of the Android market where I live, and getting a Nexus/Pixel is difficult and ridiculously expensive, but I really want the raw, native Android OS without any of the vendor's modifications, and able to update to the latest OS whenever it comes out.

If I were to buy an older, second-hand Samsung, would it be possible to root and replace the entire OS with native Android (that which you'd find on Nexus/Pixel)?  Or only some phones (if so, which)?  Or is that not possible at all?
I think you want to run AOSP like ROM on your device instead of OEM's bloated version. The answer to your question depends on the device you are using. There are a lot of custom ROMs available for devices. 

For finding these go to XDA and search for your device.
There you can find all the ROMs available. LineageOS (formerly known as CynogenMod) is the most popular one.