Hi sphesihle68
welcome to the Apple (user-to-user) Community!
Re: "Storage Full Persusting issue: ... I’ve deleted all apps, even some of the ones that come with phone".
For the first thing to do before making more space available on your iPhone, it is wise to back up everything.
That way if you find later you've deleted something you need, you'll have a way to restore it.
See Apple support's article: How to back up your iPhone, iPad, and iPod touch - Apple Support
and / or
You can store files you want to keep handy on a computer, or use a computer to transfer files to external storage devices like zip drives or portable hard-drives.
Eg: See how to: Transfer photos and videos from your iPhone or iPad to your Mac or PC - Apple Support
____________________________________________________________
Re: "I pay for iCloud 200GB every month and even that is halfway full."
iCloud is mainly for syncing files across various devices, and for device back-ups.
Although it can also store hi-res photos and videos, leaving low-res ones to take up less space on the iPhone iCloud storage is still quite separate from the storage that's available on the iPhone.
If needed: see: What's the difference between device storage and iCloud storage? - Apple Support
When you buy an iPhone. it has it's own storage amount that can not been exceeded, or added to.
Currently, new iPhones (depending on the model) provide choices of 128 Gb, 256 Gb, 512 Gb, or iTb
As you can see, you can store a little or a lot on an iPhone. It depends on choice, and purchase price.
___________________________________
Re: " .... never ending storage full issue"
You can easily check the amount of storage you have, and see what is using up the storage on your iPhone:
See Apple Support's online article: How to check the storage on your iPhone and iPad - Apple Support
The article explains how to use "Recommendations" to delete large files and to make space on your iPhone.
_________________________________________________________________
Re: "I haven’t update my software in over 2 years because of this issue."
See: What to do: If you need more space for an update on your iPhone, iPad or iPod touch - Apple Support
Eg: says:
"If a message says that there isn't enough space to download and install an update,
manage your space with recommendations or connect to your computer to install the update".
All the best :-)