Which airline is the cheapest ?
Flight prices change constantly, so there isn't a definitive answer to the question.
From Europe
From Europe, generally the best deals can be found from London (British Airways), Paris (Air France), Amsterdam (KLM), Frankfurt (Lufthansa), Copenhagen (SAS) and Helsinki (Finnair). The quality of service of these airlines is very similar and is a matter of personal preference. If you need to change plane at one of these airports, it can be considerably more hassle in big airports like London Heathrow or Paris CDG if you need to change terminal. A shorter waiting time between connecting flights can also be worth a few extra euros/pounds.
Japan Airlines (JAL) and All Nippon Airways (ANA) have direct flights from London, Paris and Frankfurt (as well as Helsinki for JAL). These are usually a bit more pricey than European airlines, but for some the quality of Japanese service is worth the difference.
There are also relatively good deals with Swissair, Austrian Airlines, Alitalia and Turkish Airlines. Some, such as Lufthansa, offer youth/student discounts.
Russia's Aeroflot almost always offers the cheapest flights, that is if you are not concerned about lower quality service and safety standards.
From the USA
The choice of airport is much more restricted than from Europe. Most of the cheap flights leave from L.A., though there are also surprisingly cheap flights then New York considering the distance.
Is there any alternative to air travel ?
If you can't stand airplanes, it will unfortunately be very difficult for you to reach Japan. Sea Travel is long, tedious and expensive, unless it is from Korea, China or Russia. Coming from Europe, you could take the train across Russia, then a ship to Japan from Vladivostok or from China. However, this requires you to get a proper visa for Russia/China, and therefore apply before you leave (visas to Russia are particularily hard to get outside organised tours).
