****As far as giving him "Out Of Cage Time" every single day, which he does need to have every single day, not only to bond with you, but also for his physical and psychological health (sitting in a cage all day long, every single day is not at all good, and it's probably what he's been doing his entire life up until this point)...I'm assuming that his wings are not clipped, is that correct?
If his wings are not clipped right now and he can fly, you need to know that the quickest way to LOSE ANY TRUST that you may have gained and set yourself way-back is by chasing him around your room with a towel, trying to catch him to get him back in his cage. This is a big no-no. ****Honestly, I think for you and for your specific parrot, the best thing that you could do to not only provide him with ample Out-Of-Cage-Time every single day and have it not be traumatic and stressful for him (or for you), and for you to start earning his trust and forming a bond with him, would be to have his wings clipped...And I really think this is almost a necessity for you at this particular point, because you're getting very frustrated, and he's not getting the out-of-cage-time every day that he needs, and when he does it's very stressful for both of you...
There is nothing at all wrong with having your bird's wings clipped. First of all, it's completely pain-free, it won't hurt him at all. Second, it's completely temporary and if done properly by someone who knows what they're doing, they will grow back in completely and he'll be able to fly again within 1 and a half to 2 months. The idea is that you make the most of every single day with him during that 1 and a half to 2 months of having him be able to be out of his cage without flying away from you...I've hand-tamed many, many birds, mostly Budgies and Cockatiels who were parent-raised and scared to death of people, and the quickest and most-effective way I've used is by-far clipping their wings once or twice and then making sure that they have a "perch" or a "stand" outside of their cage, or their own little "safe-place/space/area" outside of their cage, so in your case this would be located in your bedroom at all times...Just like his cage right now is his only "safe-space/area", as birds are extremely territorial and with a new bird that cage is the only thing that is "his", he also needs to have a "safe-space/area" outside of his cage in your room, which will be the place that he automatically goes each time you open up his cage and he comes out. The easiest and cheapest thing would be either buying or making him a "T-Stand" or "standing perch" for him that you will keep in your room, preferably right next to his cage, and this will be the place that he will automatically go when you let him out of his cage (once he becomes comfortable going out and back in on his own, and once you introduce him to his new T-Stand or standing perch). It could also be a table-top stand/perch if you have a piece of furniture in your room that you can set it up on, or one of those tabletop "play gyms", etc. I made several standing T-Stands out of PVC piping (and you have to wrap the part of the PVC piping that the bird stands on, because otherwise he'll slip right off, so the best thing to use is Vet-Wrap/Tape, or the athletic tape we use to wrap our ankles and such). PVC piping here in the US is extremely cheap at any hardware store, and you can buy it in different diameters for the size of bird...Or, if you can simply buy a standing or tabletop perch for him at a pet shop, then that's easiest...Either way, he must have a "safe-space" that is "his" for him to go outside of his cage.
***The other thing that clipping his wings does is it basically makes him rely upon you for everything...Birds hate to be on the floor, as they are the lowest thing in the room and they have no dominance at all when on the floor...So if his wings are clipped, you open up his cage, and he comes out and glides to the floor of your bedroom, this presents an entirely different dynamic with him than what you have now. You would likely be able to reach down slowly with one finger outstretched and he may very well step right up onto it, because he needs help getting off of the floor and back to his cage. These are the types of trust-building exercises you're able to do if his wings are clipped. If they aren't clipped, all he's going to do is keep continually flying away from you, and this only moves you backwards, as you try to get him back in his cage or get him down to interact with him, and then you start chasing him with a towel, etc. , and this just distances him further from you in his trust...
****VERY IMPORTANT*****
If you do decide to have his wings clipped, which I really think you should, you need to find someone to do it for you that knows what they are doing, such as an Avian Vet, a Bird Breeder, or a Bird Shop owner/employee who knows what they are doing and has done it before...And even more important is that YOU make sure that YOU DEMAND,
absolutely DEMAND that whomever is clipping your bird's wings "Only clip the outermost 4-5 Primary Flight-Feathers on EACH WING, that's it, NO MORE THAN THAT,
AND IT MUST BE DONE ON BOTH WINGS!!! This is so important that you need to WRITE THAT DOWN AND TAKE IT WITH YOU WHEN YOU TAKE YOUR BIRD TO BE CLIPPED AND READ IT TO THE PERSON BEFORE THEY DO IT!!! "Only clip the outermost 4-5 Primary Flight-Feathers on BOTH wings!!!" Right it down!!! The reason you need it done this way is #1) It will still allow him to have enough flight-feathers left so that he can glide to the ground and not drop like a stone to the ground and hurt himself, and it will allow him to glide in a controlled way, such as with direction, #2) They ALWAYS must clip BOTH WINGS EQUALLY because if they don't it will cause severe balance issues, as well as damage to his Spine (it used to be common for them to clip only one wing, and some old-fashioned bird breeders/Vets will still want to only clip a single wing, and it's a horrible no-no), and then #3) Only clipping the outermost 4-5 Primary Flight-Feathers will ensure that they will grow back in and he'll be able to fly again within about 2 months max, if they clip into the Secondary Flight-Feathers it can take up to a year or longer for them to grow back in (sometimes they must do up to 6 Primary Flight-Feathers to keep them from getting altitude, which is fine, just as long as they only cut the Primary Flight-Feathers and do NOT go into the Secondaries).
I think this is probably the best move for you, just in my own experience training and hand-taming birds who were parent-raised or who were kept in cages and passed from owner to owner, and who never formed a bond with a person before. There will probably be people who respond to me telling you to clip your bird's wings in a very angry, negative way, as there are a lot of bird owners who are strictly against EVER clipping a bird's wings for one reason or another, which is fine for them and their birds,
it's every bird owner's personal choice. There are many excellent and very experienced, life-long bird owners who keep their bird's wings clipped full-time, because it's what is best for their household/lifestyle for one reason or another. And that is totally THEIR CHOICE. What is important to keep in-mind is that clipping a bird's wings does not hurt them one bit, it's no different feeling-wise than getting a hair-cut as long as it's done by someone who knows what they are doing, and they first check for any Blood-Feathers before they clip. Their feathers have no nerves or feeling. And they grow right back in just like hair as well. And keep in-mind that I am no suggesting or recommending that you KEEP your bird's wings clipped forever, I'm only suggesting that you clip him now, and then maybe once more once they start getting long again, just so you can make some progress with him and it will be a bit easier and less stressful for you and for the bird. I too believe that birds need to fly, and all of my birds are fully-flighted and not clipped,,,however, that's my choice, and everyone has their own choice...And if you have your bird's wings clipped in just the way I'm suggesting, it will be painless, completely temporary and actually very temporary, at most 2 months or so per clipping, and it will only serve to help both you and him...