So being my second trip back to Japan now, original plan was sitting in Tokyo again for about 5 days. We have made an extension for our trip to the tune of 4 more days. We're open to heading out of the city to a different part of the country. We have done Osaka and Kyoto already. Any tips on a different part of Japan that we should check out (that won't break the bank). Looking at Okinawa maybe, but maybe its too short for 3-4 days?

That's a very broad question. Possibilities are endless. Depends on what part of the year you're going, your interest, budget, whether/not you'd be interested in using a train pass (it appears you're not). Okinawa, Kyushu, Sanyo region, Gifu/Nagano, Hokkaido... possibilities are endless.

When are you going? Do you plan to arrive and depart via NRT or is another airport possible? What would you like to see and do?

That's like asking "I went to New York City last time, what's another good place in America to visit?"

I say go for Nagoya! ^

Understand its a pretty broad question. I guess budget is a low as possible. We're basically back-packing it in hostels so far.

We can exit Japan from either Tokyo or Osaka.
Going at the end of April.
Not a museum/temple person
Looking mainly for experiences. Biking around Kyoto was a splendid time. We're late twenties if that helps at all.

Sounds like Tohoku is the place for you!

I think you might like Okinawa then. It'll be just before their tsuyu season. It'll involve another flight, although you might be able to get a decent fare on an LCC like Jetstar.

Kyushu would be great. A lot has been talked about with Kyushu on this forum.

+1 to Okinawa, it's about as different as it gets while still being in Japan. Flights are cheap too if you can use the JAL/ANA passes (any flight for Y10k).

Alternatively, pick any of these that sound interesting:
http://en.wikivoyage.org/wiki/Off_th...track_in_Japan

I am guessing that you are looking something different from Tokyo, Osaka, and Kyoto? I agree that Okinawa will be good choice, tropical island feel which is different from Tokyo, Osaka, and Kyoto. There are places you can visit in Okinawa to experience local Ryukyu people�s culture and history which is very different from what you saw at Kyoto.

Along the similar reason heading north to Hokkaido will be different from Tokyo, Osaka, and Kyoto. Vast open space where you may not think place like this exists in a small island nation of Japan. Experience local Ainu people�s culture and history which is very different from old city Kyoto.

Another place different I can think of is Nagasaki. Nagasaki is where Christianity has flourished once, and when Japan closed the door to outside for three hundred years Nagasaki port remained opened to Dutch. Also, historically Nagasaki had trade with China. I do think Nagasaki has different feeling from Tokyo, Osaka, or Kyoto because of that.

+1 on Nagasaki, or all of Kyushu for that matter. Flights from Tokyo to Fukuoka or Nagasaki shouldn't be too bad. I usually use the JR Rail Pass but you may or may not want it. Should be warm in late April.

I also fell in love with Hokkaido but don't know what the weather conditions would be like in April, I was there in the fall. Probably still cool. Even if you don't go to the northern part of the island, Hakodate and Sapporo are interesting and accessible.

Might I suggest the Tomb of Jesus (he was Japanese, don't you know?) or the adventures to be had in Mineland? Train up to Hachinohe and then a rental car around for a day or three is worth it IMO.

what about the cabbage factories in Nerima?

You can also find the Grave of Moses in Japan (aka the true Holy Land!)

Japan has it all!

I am not sure if Nara would interest you but my employer (in Nagoya) sponsored a day trip to the deers. It was a unique experience.