I really like SomeShinyObject's lead by example suggestions. Another angle is to focus on minimizing the fear of failure, by reframing what success looks like. Give him a very small easily achievable goal, praise mightily when he succeeds, then build on that success. I've broken a couple examples down as small as possible, obviously use your own judgement. The key is that each step is a victory and to reinforce that success with praise. The ultimate goal is achievable through consistency and patience.
The coloring example:
Clear the table. Ask him to pick his favorite page from the coloring book and take it out of the book so he can focus on it. Ask him what part of the drawing he thinks you guys should color. Agree thats a good place to start. Ask him what color he wants to use. Say something nice about the color he picked. If he's not playing along, make wacky suggestions "Maybe we should color the sky green?". If he participates and colors the part he wanted, tell him he did a great job. Ask him if he wants to color another part. If not, come back to it again later.
The food example:
Give him his normal food, but put a bite-sized piece of the new food on his plate. Don't make an issue of him eating it or not. Even if he objects, just keep doing it each meal, eventually he'll accept it. Praise this, move on to the next step, ask him to hold the food in his hand. just touch it, no eating. great job. have him smell it. Accept that as a small victory. Ask him to give it a little lick. eventually have him put a piece in his mouth. chew, swallow, etc. he might spit it out, but he still gets a "good job, thanks for trying it". My kids went from throwing a tantrum when green beans were on their plates to eating them as if it was totally normal in about 3 months. Each additional food gets a little easier.
The balance beam example is a really clear one:
Start with a line on the ground. Move up to a beam on the ground. As he becomes comfortable with each increase to challenge, praise him and increase the challenge. If it gets to a point where it's too much, back the challenge off. Or try a slightly different challenge, like instead of increasing the height, put something on the beam he has to step over, or do it blindfolded, do it holding something in one hand.
A final thought, at around 4 years old we noticed our son was strongly averse to certain stimuli. Food textures, noisy chaotic environments, some physical sensations. He was ultimately diagnosed with Sensory Processing Disorder, basically he experiences stimulus at a much higher intensity than other kids. Before we understood this we would get frustrated with him because he would be afraid of things other kids had no problem with. Understanding his condition doesn't solve it for us, but it helped us shifted our perspective and parenting methodologies. Everyone is happier now. I don't presume to diagnose your kid, but if you're seeing a pattern of behavior that deviates from other kids his age (or especially his siblings), it's worth a look.
Edit: Responding to @anongoodnurse, I'm basing this advice off of my own subjectively successful parenting experience. For some kids, I think the fear of failure stems from a sense of being overwhelmed by a big or complex problem. My answer above gives examples of breaking down a big problem (for a kid) into manageable chunks. The praise is just immediate reinforcement when they make some progress towards the ultimate goal, it isn't the solution itself. For a kid that is unsure of themselves, praise gives them a motivational boost to keep at it. As their confidence improves and they become self motivated, dial the praise back. As far as the specific phrasing of praise, I'll leave that to its own question.