I'm planning my trans-mongolian/siberian trip and I'll end up in Beijing. I want to know if it's possible to reach Japan without flying (ideally Tokyo).
There are ferries between at least these points, China on the left, Japan on the right:
Here's some other links with overviews and details:
Oh and I almost forgot my favourite! If by "mainland Asia" you want to include Siberia, there is even a ferry from Sakhalin to Hokkaido!
Alternatively, you could take the ferry from Tianjin to Incheon (South Korea), spend some time in Korea, wind your way down to Busan, and then take the ferry to Japan from there. See this excellent post for information on the ferry to Japan from Korea.
I recently met a German guy in Korea who was traveling around the world without airplanes, and that's what he did.