I dunno, at that point, are you really doing math? Math is proof. Now, granted, nobody expects you to know exactly how everything is proved. But there is an expectation that you can prove most of the stuff. Otherwise, it's very easy to stray from the truth into the plausible-sounding, but incorrect.

That said, you're absolutely correct that more justification and motivation is important. So much of math can be taught with problems from physics, computer science, etc. Perhaps a good book for you would be Concrete Mathematics by Knuth? I haven't read it but people swear by it.