I just stayed at a place I found on Airbnb (in early June 2014). It's called Casa El Camino and is run by a former pilgrim, Rosa, with deep family ties to Fisterra. The place is located a quick 10-minute walk from the center of town on the west side of the cape - which means you get to see the sunset from the living room! Rosa has private rooms with shared bathroom and kitchen for 20 euros per person. She is also fluent in English, Spanish, Gallego, Swedish, and I think German and French.
Find it and book here:
https://www.airbnb.com/rooms/1502939?s=oyJ3
Tip: For the best rates, book just your first night via Airbnb then email Rosa directly if you want to extend your stay to multiple nights. And be sure to try out the Italian restaurant Rosa recommends, Peppone. Fantastic food with a 12 euro / high value menu Monday through Friday.
I also stayed one night at Albergue Cabo da Vila and can recommend it, as well. The staff there are lovely and the private rooms (shared bath and kitchen) are comfortable. But to be honest, I was ready to be a few steps off the pilgrim trail by the time I reached Fisterra.