Para solicitar la baja por paternidad, ¿Es necesario que los dos estemos juntos empadronados?

No le van a pedir el empadronamiento, sino el certificado de nacimiento o el libro de familia, donde ponga que es el padre.

No, yo mismo tuve un hijo hace menos de un año y sigo empadronado en mi pueblo (pese a que resido en la ciudad donde trabajo). El libro de familia ya no lo expiden, por lo que necesitarás certificado de nacimiento del bebé, y un certificado de la empresa donde trabaje, entre otros documentos.

Dado que no constamos en el mismo domicilio (aunque sí vivimos juntos), fue necesaria mi autorización por escrito para empadronar al niño: "legalmente" mi residencia consta en otro lugar, pero en la práctica residimos juntos. Pero como esto no aparece en ningún documento, a la hora de empadronar al niño tuve que firmar para empadronarlo en nuestra casa. Esto se hace para evitar casos en que los padres estén separados y puedan llevarse al niño sin el consentimiento del otro.

En resumen, en vuestro caso no es necesario el empadronamiento ni vivir juntos para la baja paternal, lo sé por experiencia propia.