1 -> Supongo que para la parte del servidor tengo que usar MySQL para la base de datos, y PHP como intermediario, ¿correcto?.
Eso depende enteramente del servidor y de los drivers de bases de datos que soporte PHP / Lenguaje server-side.
De todos modos, tal y como puedes usar MySQL tambien (en la mayoria de los casos) puedes utilizar SQLite.
2 -> ¿Existe algún host gratuito que permita peticiones remotas a la base de datos desde los teléfonos móviles de los usuarios?.
La mayoría de los hosts niegan accesos externos a la base de datos.. por motivos de seguridad. De todos modos, no es muy lógico (ni seguro) incluir las credenciales de la bd en una app destinada al publico.
3 -> La información que se envía del servidor al móvil, supongo que va en formato html, y yo diseñaría una función que extraiga la información. ¿Es así, o es mejor de otra forma o se usan otros formatos?.
Puedes usar cualquier formato de salida.. simplemente tendrás que obedecer el protocolo HTTP en caso de hacerlo en un servidor web. En este caso, quizás sea mas recomendable XML o JSON.
Saludos