Normal is pretty easy, you shouldn't expect to run in to problems unless you take risks, are unlucky with drops or rush through the game(run past mobs without killing them). There is nothing wrong with clearing all, though you will most likely get better xp(per hour) if you do not clear all and you will definitely get better drops and gold if you skip some of the random dungeons and focus on getting further in the game. Also due to the way maps and dungeons are randomly generated you can't expect to have seen all dungeons and events even after a couple of full clears.
My personal approach is to focus on getting the quest done, killing most mobs I meet on the way, doing all events I run in to and now and then going in to a random dungeon. If I run in to a part of the game that is to hard when playing solo then check AH for replacements for my lowest level items or run an earlier quest again to gain xp and items. I am now at the end of act I on hell and everything is going pretty smooth, but I have done some backtracking so I could play with others now and then.
It is very easy to go back with the way the quest system is designed so the best way to progress is to push forward til you hit a wall(game getting to hard to progress) and the go back a bit and give it a try again, then repeat until you are on Inferno :)