We got the MOST effective improvement in our son's brushing habits by moving away from the "kids tooth paste" in bubble-gum-tooti-fruiti-cherry-so-sweet-you-wanna-puke flavor to just plain old non-flouridated baking soda tooth paste. He still wants to suck on it a little bit, and chews to some extent on the bristles, but that one change alone was like a night and day difference for him. He'd of course rather do it himself, but he doesn't seem to fight as much when we step in and help.
Lately I've been using Vic's modelingVic's modeling idea to great success. I prep his and my toothbrush at the same time (with the same toothpaste) then we sit across from each other face to face and brush together. I step through the various parts and he at least tries to do them. And it keeps him distracted from eating it!