To answer the question of accommodation accessible by public transportation, I found three hostels:
- The international hostel of Forillon is located near the entrance of the Forillon park, i.e. near the intersection of road 132 and the Bd de Grande Grève. I did not try it but it is accessible with the ReGIM line 21
- The hostel La Merluche is located downtown Gaspé, not far from the departure of the Orléans Express (Adams hotel) or the ReGIM bus stop (in front of the Provigo supermmarket). It is only open during the high season (it opened around June 10th in 2015)
- The hostel Griffon Aventure is located near the small town of Rivière-au-Renard, accessible by ReGIM line 21. The hostel is very remote but pretty nice and ecological (water is from tanks, it is not plugged to the network) - and one room is actually a boat, see below.
Since the ReGIM and Orleans Express only come once a day each, it is rather complicated. To catch the Orleans Express back to Quebec City/Montreal, it was easier to sleep at La Merluche the night before (the bus leaves around 7AM).
However, the good news is that while public transportation is very weak in this remote area, it is rather easy to hitch-hike in this area (distances are big, it could easily be tens of kilometers for a "short" trip). In my experience, I could find a ride from inside the Forillon park towards Gaspe with the first car I saw (in early June, just before the high season starts) and people in the hostels told me similar stories where people would drive up to 50km out of their way to drive people to the hostels. And most travellers I met relied on hitch-hiking.
For access from/to Rimouski (the first connected town towards Quebec City and Montreal), the bus is expensive and comes only once a day but there are a couple daily rideshares findable on Facebook groups or Amigo Express or even a possibility to hitch hike all the way to Rimouski within a day, maybe with many rides (this is normally a 4-hour drive).
So with a bit of patience, it is actually possible to move around and reach affordable hostels. However, take a map of the area or prepare a bit where you're going since the Google Maps or OpenStreetMap do not have very precise locations of hostels.
A boat hostel "room" at Griffon Aventure - CC by Vince