Beginner Self Study Textbook

I'm a beginner to Japanese, I know all the Kana, but only a few words and phrases. My goal is to get up to a N2 level reading, speaking, and writing by the time I'm (hopefully) off to college, giving me around 4 years. Note that I don't want to study to pass the test, I want to become as fluent as I possibly can in Japanese, that's just my goal. I'm looking for a starter textbook that will suit my needs, any recommendations.

Also, will I need a separate textbook for Kanji and grammar, and should I attempt to learn both at the same time?

Great. It sounds like we're on the same level. I'm a college grad and never been in Japanese classes. I know kana but Katakana I'm sketchy on. I know kanji and other few phrases and I can not read sentences at all really because of the kanji. I would say download Genki (a Japanese textbook), Download a flashcard or memory game in japanese, watch some Japanese movies, listen to Japanese radio stations, and you'll need a grammar text book as well. Don't forget a japanese-English dictionary in (romanji or kana).

To tell you the truth, I've spent almost a year on this language and I can't speak or read complex sentences. I'm memorizing Kanji at the moment using Anki (Flashcard program). I'll soon cycle and watch movies and text book grammar again.

If anyone else can help me with a better strategy or software let me know.

**P.S. - All of books/software mentioned above I use currently.

Strive for proficiency, not fluency.

Here's a list of books I have used in the past, along with my opinions on them. The OP won't need all of those, but this post can be more helpful to others if I don't tailor it explicitly to what OP asked for. If you go to Google Books and enter the titles, you should be able to see previews of many of the books listed below.

Books to Buy

Japanese for Busy People by AJALT → It's an okay textbook and what I started out with. If you have a good teacher and a small-ish class, it's a good way to get started, I think. It can also be a nice base for self-study. If used that way, it can help to keep you focused. It has lots of mechanical writing exercises and chapters are tied together with a simple storyline. Once you're through with the first book, you can go to Japan on holiday for one or two weeks and do stuff like order at a restaurant, buy things, etc.

A Dictionary of Basic Japanese Grammar by Seiichi Makino and Michio Tsutsui → This is a useful companion whenever I'm doing writing homework and am unsure of how to use a particle or a specific grammar point.

Making Sense Of Japanese: What the Textbooks Don't Tell You (aka Gone Fishing) by Jay Rubin → Buy this book. It does what it says on the cover. It covers a number of things where teachers like saying "this is very difficult; just memorize it."

Let's Learn Hiragana by Yasuko Kosaka Mitamura → It shows hiragana using their stroke order and then lets you practice them. It expects learners to do their own writing drills. There are writing exercises at the end of each chapter that can also help build up a basic vocabulary. There are also some puzzles and supplemental exercises at the back of the book.

Let's Learn Katakana by Yasuko Kosaka Mitamura → The companion book to Let's Learn Hiragana. Same deal as before. It also has a large section on katakana spelling rules.

Basic Kanji Book 1 & 2 by Chieko Kano → It introduces kanji with gentle foreplay before it proceeds to rape you with them. I like this book because it shows common kanji compounds and has the standard set of info (readings, stroke count, practice boxes). Works great in conjunction with Anki and will teach you 500 common kanji. After that, you're on your own. Kanji are split into chapters. Each chapter has a common theme.

Books to Consider

Kanji ABC by Andreas Foerster → Approaches kanji by splitting them into graphemes (something like radicals), but it didn't work for me, because I prefer learning kanji as compounds rather than characters floating around in a vacuum. For people who like rote learning, this is the book to buy.

A Guide to Remembering Japanese Characters by Kenneth Henshall → This is nice if you want to learn how kanji ended up looking the way they do. It's best used as a companion to something like Basic Kanji Book. The author includes a short mnemonic as a memory aid. I use this book when encountering a kanji that I want to know more about. For example, it says that the "田" in "思" is a brain and the "心" represents feelings → feelings in one's brain → a thought.

The Kodansha Kanji Learner's Dictionary → Had to buy this for a class but haven't made much use of it yet. It will probably come in handy in a few weeks when I outgrow Basic Kanji Book.

Books to Avoid

Let's Learn Kanji by Yasuko Kosaka Mitamura and Joyce Mitamura → Spends 87 pages to teach you kanji radicals and then drops you into cold water. It teaches you 250 kanji by stroke count and has exercises at the end of each batch of 15 or so. Basic Kanji Book is better, because it will teach you more kanji and group them by a common theme instead of doing it by stroke count.

Remembering the Kanji by James Heisig → You learn ENGLISH words for kanji using stories, and then have to work through a SECOND book to learn readings. Kanji are introduced in a completely random order. Needless to say, it's a waste of time and doesn't work. I returned this book a week after I bought it.

Japanese Demystified: A Self-Teaching Guide by Eriko Sato → "To say X is Y, Japanese uses the form XはYです" ... nope. Avoid. I kept this book mainly because it had so many exercises and mini-tests.

Oxford Basic Japanese-English Dictionary → Had to buy this for a class, but it's not worth it; Denshi Jisho - Online Japanese dictionary is better.