Predatory behavior is going to be very difficult for you to "train" away as will be the "gift giving". If the predation seems to be mostly at night, one suggestion might be to keep him in at night. Obviously, if his skills are just as strong during the day then you will have to decide if it is worth going through the potentially longer task of trying to "correct" this behavior or simply make him an inside only cat.
A couple of suggestions you may think about:
1) An enclosed patio or outside enclosure. Many of these are found in pet magazines and some pet shops and are basically mesh or fenced enclosures (like a closed in canopy) that can serve as an outside "play pen" but prevents access to rodents, birds and other cats.
2) Ensure that there are no bird feeders or open trash cans around your property that might serve as open invitations to birds and rodents making predation that much easier.
3) DO NOT attempt to reduce prey numbers by placing rodent bait or traps as they often end up hurting the cat rather than doing anything to inhibit prey from coming near your home.
4) I often use water spray guns and keep several handy around the house so that whenever one of my cats is doing something I don't like, a quick spray of water in their direction will often send them running away and stopping whatever they are doing. Now my cats know when they are about to get sprayed so that I only need to grab the spray gun and they usually stop (whether it is scratching the furniture, jumping up on a forbidden counter top, chewing on one of my shoelaces). You could try something similar so that the moment you see him with a bird or rodent, spray him before he can even bring it anywhere near you. If you can control his activity during the day, then you have a better chance of catching this and intercepting him rather than waking up to a "gift". Remember that animals respond to immediate correction rather than correction to a behavior they performed minutes or hours ago. Don't spray him for bringing in a rodent 3 hours ago, he won't understand why he is being corrected. The rodent or bird must be in his mouth for him to understand the correlation.
There are a few books that you can purchase at the book store regarding feline behavior and why they do what they do, including some additional hints on behavior modification. But recognize that he thinks he is doing something helpful for you and not trying to be "bad" so you must treat the behavior as equal to anything else you do not want him to do and not give this behavior "extra" punishment or consequence, he won't understand it and he could become antisocial to you altogether.
Hope this helps get you started. I'll keep an eye out for any further requests from you.