Welcome to the forum! First of all, what is his name? The one he had from before I mean and not a new one that you might like better -let me explain this in more detail. There are studies that tell us that parent parrots name their babies in the nest and that babies continue using the same name or a small variation of it all their lives to refer to as well as introduce themselves to other birds - this tells us that parrots not only understand the concept of proper names but that they actually use them so I always recommend people who take in adults to continue using the same name they had before because giving them a new one will only confuse the bird and delay the process of his/her getting used to its new home - which is, actually, much longer than people realize. He IS tame - all handfed birds are. He is just not used to you. Parrots are not like dogs, nature did not give them a submission gene or an aggression one so they only attack for defense or protection OR when they are taught by humans who don't know how to handle them that biting is the only resort they have to get their point across - which is a good thing BUT the other side of it is that they are also not 'programmed' to be people-oriented and humans need to win them over. You've only had him a few days and he still doesn't trust you so you need to convince him that you are not only no threat to him [which you kind of messed up when you toweled him] but that you want to be his friend. This is done by respecting their wishes, not forcing them to do anything they don't want to do, having a HUGE amount of patience and simply loving them regardless of what they do or don't do.
Now, as to the gender. Look under his tail. You will see shorter feathers that 'cover' the beginning of the longer feathers that make the tail. These feathers [they are called 'tail undercoverts'] will be red like the tail BUT, in females, you will see a very thin grey edge at the very tip while, in males, they are completely red from beginning to end.
The movement and vocalizations you describe are, indeed, what you have already surmised: he is asking you to let him out. Now, I do realize that you tried and it seemed as if it did not work out because he did not go back into his cage for eating BUT birds don't commit suicide by starvation so, in reality, if you had waited long enough, he would have gone back into his cage to eat. BUT, given that his cage is so small, it is entirely possible that it was used only for sleeping and, if this is the case, he is used to eating outside his cage. I know that you said you are against this practice but I would strongly urge you to reconsider your position on this because ALL parrots eat outside their cage. They might get the main meal [gloop, pellets, seeds, whatever] in a bowl inside the cage but they all eat stuff outside. My parrots get their breakfast [gloop and raw produce] as well as their dinner [nuts and seeds] IN their cages but the ones that live in them [I have some that don't] actually eat produce outside of their cage. This is normal for them and, in truth, feeding them raw produce while they are perching outside a cage while you eat it standing in front of them, is the BEST way to get them to eat a varied diet [and grays are notoriously picky and difficult to convice to try new items so this is actually a GREAT help for the owner]. You most likely don't want him to eat outside the cage in order to keep things clean but I might as well tell you that it's absolutely futile. Parrots throw food all over the place and there is no changing this because it's part of their hard-wired behaviors to fulfill their ecological niche. Ergo, I suggest that if you are somebody who is a stickler for absolute neatness, you start looking for ways to minimize the cleaning [like putting a large cover on the floor around the cage, Plexiglas to protect the walls, etc]. It's no use fighting certain 'undesirable' parrot characteristics, it's best to resign yourself to the fact that you are living with an undomesticated animal and look for ways to get around them.
Now, as to his new cage. You should not move him - per se. It's best for him to get into it on its own and, in order for this to happen, he needs to be out of his little one and tempted into going into the new, larger one. It might happen the first day you let him out and it might take days and even weeks so arm yourself of patience because, in order for this to go smoothly, he needs to decide the move on its own and it might take some time. Put the new cage next to the little one [so he can see it all the time and get used to it] and 'fix it up' with different kinds of perches [never dowels! use things like natural tree branches, boodas and sweetfeet], his water and food bowl and toys [start with soft, colorful 'chewies' like this one:
http://www.drsfostersmith.com/product/p ... atid=35526]. If you are going to use one with a bell, make sure the clapper is too big for the bird to get into its beak and that the whole thing is made out of stainless steel. I would also tie a branch or a couple of them to the side of the cage on the outside so he can climb up - they love heights and they love branches.
His cage should be tall enough that his roosting perch is at your eye level when you are standing [making it shorter will give him the feeling that you are a predator looming over him]. It should be near a source of natural light [a window, French doors] so he can get the exposure to dawn and dusk necessary to keep the solar schedule but there should also be a source of artificial light overhead [don't use the bird lights that clamp on the cage, they are too close to their eyes and dangerous to their vision]. It should also be either against a wall or have a solid cover in the back [like a thick material draped over it] -this makes them feel safe because they know that a predator will not be approaching from that side.
Now, how to go around getting his trust and love... First of all, don't stare at him [only predators do that]. You will be able to look at him straight once he is used to you but until then, look at him out of the corner of your eye and don't approach him in a straight line, do it casually so he doesn't feel you are stalking him. Spend as much time as you can in the same room as him - talk, sing, whistle while you do 'your thing' [cleaning, computer, phone, etc] and, every now and then, offer him a treat and, when he takes it, praise praise praise him profusely. Parrots are masters of the human body language and tone of voice and even when they don't know what we are saying, they can tell by the way we say it and move if this is a positive interaction or a negative one. I always use a cheery, high pitched tone of voice with them normally and it works out for me [all my birds have come to me from somewhere else so I've had to 'win over' every single one of them]. But, the most important thing you can do for him is to follow STRICT schedules and routines doing always the same things, in the same order, at the same time every day - no weekends, no holidays, no sick days, no nothing -every day has to be the same, starting at dawn and ending at dusk.
I've had all kinds of animals but, in my personal experience, parrots are the hardest -by far!- to keep happy and healthy... especially grays!