Hi Nicole,
I stayed in Villaviciosa for three nights, 2 of them at Hostal Cafe del Sol (tel 985 89 11 30). It is clean and cheapish, and is the one recommended in most guides, its on the camino, if you get a front balcony room you watch the pilgrims go by. The bus station is no more than 150 meters away, if you come out of the back entrance you are on the camino, turn left(into town) and you will be going to the hotel, you will see a tourist information on your right as you are walking, maybe ask there about credencials or even at the hotel,or even if you ring them they may be able to help. Villavicioasa gets busy at weekends and accommodation can be hard to come by, places are booked up in advance.
There are no trains, i asked this question at the tourist info, i had to go into Gijon to look for some new walking shoes, the response was laughter, then "no". But there are plenty of buses from Gijon, some go faster routes by at least half an hour, so keep an eye on that when you arrive at Gijon bus station. There are a couple of large churches near the bus station, so if you have time to spare check them out, the camino goes through this area, they may have credencials.
Buen Camino
Mike