What I've been doing is listening to podcasts with native speakers talking in them. You hear the real thing and eventually you can understand it.
As a beginner, practicing with a native speaker is...well...kind of a waste of both your time and the person helping you. Learn enough that you can hold some sort of a conversation and just have fun talking with them and they can correct you and improve your speaking skills. I highly suggest you work on listening first and know enough phrases that you would be comfortable saying them and know all the kinds of responses you will get. Look through a phrase book and the dictionary and use a flash card program to practice and make some flash cards you can take with you to school or work to practice in your spare time. Get an ipod so you can listen to Japanese music and podcasts in your free time and a cd for your car.
That is what I've been doing, and it's been going pretty well. I still don't think I can hold a conversation, so I have a way to go, and it's been about 4-5 months, just to give you an idea. I can say a bunch of phrases and remember many nouns and verbs, and I know about 900 kanji (english meanings) and most of the kana by heart. So it's possible. But you can't give up. I'm starting to get lazy about it, so I really need to work on that xD