8th March may not have blossomed at Tokyo since it does not warm up over there so soon... Sakura bloom in a particular temperature range.
How many people? You can consider Palace Japan as well. It is a short walk from Minami Senju stn. Accommodations in Shinjuku would mostly be expensive. As you are looking at a Khaosan hostel, I reckon you looking for under 4k a night places.
All 3 Shinjuku/Harajuku/Shibuya?? Might be a little tough, depends on how much you like the stuff the shops have in each area.
Tsujiki Auctions, you would probably save more by spending the nite at a Mangacafe nearby (not to mention it is an "experience").
EAT!! There is lots of good food (sushi especially) at Tsujiki market area. My personal advice would be to buy whatever you really fancy as long as you are within your weight limits for luggage and budget. Not everything can be bought somewhere else. Most and I stress MOST okashi can be found at Ameyoko's niki no kashi cheaply.
There is a temple nearby Tokyo Tower.
I recall is from convi store....
One Piece stuff I last know of not in Tokyo city limits
They give plastic bags if it is needed, depends on the department store they might charge. Bring a couple of your own bags wun hurt.
Not as many trash bins as here. Note that trash needs to separated in Japan.
March is good! No problems.... maybe slight concern of rain
Where is your planned accommodations are in Kyoto? Do they have pickup service?
Ryokans serve dinner as a set but I do not think it is kaiseki for most ryokans. It is a normal washouku set.
I would say DON'T eat Kobe beef for it's sake. Just look for "和牛" (wagyu) places within your budget. I know of a place in Shinjuku where a foodcourt (but extremely gaijin unfrenly) has good wagyu burger steaks.
Tokyo banana, available at Tokyo station to cover the different flavours. I do not fancy it but it is pretty nice.
There are few places to do sight seeing in Osaka besides Osaka Castle.