I would go with the undersized bike method as Sheldon Brown recommends.
Basically, get a bike that's a bit on the small side (and has at least one brake lever) and remove the pedals (and maybe also the cranks), so that he can have his butt on the saddle (seat) and both feet firmly on the ground with knees slightly bent. That way he can run with the bike under him. You might be able to get a bike with a compact frame design (sloping top tube) and set the seat really low instead of having to actually start with an undersized bike. Starting out on a grassy surface would be a good idea, but a stretch of clear unoccupied pavement/asphalt (such as a parking lot) would work quite well, too.
At first he'll just use his legs and slowly get a feel for how the bike moves and balances, but as he goes faster he should be able to pull his feet up from the ground for a longer and longer time. When he's comfortable with how a bike balances (able to coast and steer without keeping feet on the ground), put the pedals back on the bike.
Might a good idea to have him wearing a helmet and gloves, and maybe also kneepads, but only if they don't make him more nervous. That way if there's any problems it might be less traumatic and more likely that he feels okay getting right back onto the bike. Any other protective gear would be overkill, you tend to catch yourself on your hands or hit your knees when you fall off of a bike.
After he's got the balance right, even with the pedals on, probably good to move to teaching a proper mount and dismount so that you can set the seat at the proper height. On a cruiser or dutch style bike you can probably get away with keeping your feet on the ground when the bike is stopped, but in general you should mount by grabbing the brakes, putting one pedal at a 45º angle forward and up, using the pedal to step up to get onto the seat (and to get your other foot onto the other pedal), and almost simultaneously release the brakes so that the bike starts to move forward. Dismount similarly (with brakes engaged and using one of the pedals to step off).
There's a longer list of skills he'll need to learn before riding safely on roads, but balance, steering, mounting and dismounting is a really good start.
Through all this, he needs to keep patient. The simple reality is that it takes a while because you're trying to train your body into modifying its reflexes a little (so that you steer into a fall to keep from falling to the side). If you try to think your way through balancing on a bike you'll fall over a lot because thinking is too slow, you need to retrain reflexes.