Pues al final, después de unas 3 horas de prueba y error me ha funcionado de la siguiente manera.
- La consulta SELECT normal, como cualquier otra, nada de codificadiones.
- En la Base de datos, en el campo ruso si que tengo puesto koi8-r, para poder visualizarlos en la propia base de datos.
- Y para mostrarlo correctamente en la página los 3 idiomas a la vez he puesto justo despues de la conexión con la Base de datos esto: mysql_query ("SET NAMES 'utf8'");. Eso sí, las conexiones ya las hacía con mysqli y me ha tocado regresar al antigua forma ya que no sé cómo hacer lo mismo pero con mysqli.
Espero que a alguien le sirva.
Saludos!