I'd like to entirely replace Android on my phone, which I plan to eventually root. I've learned so far that Linux Deploy can be used to run a full Linux distro alongside the Android OS, but really I want to replace Android OS. I'm willing to put Mobian (mobian-project.org) on there or just pure Debian. Is this possible yet in 2021?
Simple answer : NO
Reason : Hardware drivers are proprietary Building them without the source is extremely difficult Requires a lot of expertise and time Not possible unless you have low level access to your device hardware (Meaning being able to flash without fastboot or edl)
So yeah stick to the answer that, NO you can't replace Android entirely with Linux.
Something you can do is :
You can of course try using other AOSP based OS like Lineage OS which are build on AOSP so it is compatible with the default kernel for you device (This is also only possible if it is already built for your device)
If you want to run Linux alongside Linux there are a few ways.
Like you said you can use Linux Deploy. (I have personally not used this)
Or you can use PRoot with Termux which is a user-space implementation of chroot thus you can a virtualized Linux environment (similar too using chroot) but without the need of a rooted device. You can either use PRoot with scripts created by others via AnLinux or Andronix.
Or you could always learn how it works and manually set it up :>
And no as time goes on things wont change. You won't be able to install Linux in a Android device. This is not due to hardware incapability but rather it is how the Smartphone industry works.
I could be entirely wrong but here i go.
With postmarketOS, and recent years, people work hard to bring linux to phones. One of the examples is OnePlus 6 - one maintainer worked hard to get it running. But, here we are. It's not yet really in a daily-driving state where one can replace it, but for example calling works. So to answer your question, you could but would you be happy with this yet buggy state of linux?