This screams dysgraphia or dyslexia to me.

You might try these instead of sitting with pencil and paper:

trace letters on fine sandpaper
trace letters in the air using big, wide, sweeping motions (engages major muscles instead of fine motor)
trace letters on an iPad or draw them in a drawing app

These helped tremendously, but mostly it just took time. His writing was basically illegible until fourth or fifth grade when his motor development caught up a bit. Physical therapy helped tremendously.

~Lisa
http://www.lisaabeyta.wordpress.com/