I remember an interesting thread about bikes last summer. Seems many GT kids have trouble learning to ride. With my DD8.5, her perfectionism got in the way BIG TIME. She was almost 8 before she could ride confidently and it took two years to convince her that it was worth trying. If we had not pushed, I know she would still be using training wheels!
My little guy is 2.5 and he has the same thoughts on bikes as your 4 year old. He has a tricycle (very small) and a ride-on Thomas the Tank toy that goes 2 mph with the push of a button. He will not go near either one. Tried each once and was completely terrified. We pass bikes and ride-on toys in stores and he won't even look at them. I do not have any great advice, just a little bit of sympathy.