Not sure if this is repeated in the responses above but I will mention my experience. I cannot talk about the cycling component of the question.
There is indeed a direct flight from Tokyo to Wakkanai once a day on ANA. I took that flight in November 2019 and it is a very pleasant flight. You arrive at Wakkanai Airport around 12:40pm. I recommend the direct flight straight from Tokyo.
Day 1: Completely doable, but refer to the Heartland Ferry Schedule.
http://www.heartlandferry.jp/. Depending on your visit, ferry service is very limited especially in winter. Also, the ferry departures do not correspond to the airline arrivals at the airport. My advice is to take the bus to Wakkanai and get off either at or before Wakkanai Station (
http://www.soyabus.co.jp/airport). Then walk to the ferry terminal. The walk is through an industrial area but there are sidewalks. The ferry ride is about 1.5 hours. At the terminal, you can purchase tickets at the vending machine.
Day 2: Not sure where you are going within Rebun, but stay at a hotel near the ferry terminal (there are two or three hotels). There is a bus stop in front of the ferry terminal that takes you to various locations on the island.
http://www.soyabus.co.jp/routebus/rebun. Cycling in Rebun might not be recommended because of the terrain. Also, if you are going to the base of Momoiwa, you have to go through a tunnel where cycling might not be permitted.
Day 3-4: I would take the ferry to Oshidomari (the main town) of Rishiri Island rather than the smaller town. In my experience, driving is almost essential given local landmarks and places of interest are so remote. I know in your message, you will only walk or cycle. If you can cycle your way around the island, there are pretty good trail and path systems.
http://www.soyabus.co.jp/routebus/rishiri.
You did not mention when you are going. I did the research for hotels and all hotels do not operate between October to April/May. However, I am assuming you are going in the summer since you will be cycling.
I have attached links to the Soya bus network which provides private transportation throughout the Cape Soya area. Any questions let us know. I have traveled extensively in Wakkanai, Rishiri, and Rebun in November 2019 and I know you will have an amazing time.