My husband is a refugee in Papua New Guinea and has been issued a refugee travel document, Titre De Voyage by the Papuan government.
Are there any countries in the EU where he can enter visa-free/visa on arrival - preferably Germany?
Travel Stack Exchange is a question and answer site for road warriors and seasoned travelers. It only takes a minute to sign up.Sign up to join this community
If you are an EU citizen and your husband is not, you have a right under EU regulations to travel and work in any other EU country and to take your husband with you. (Your own country is an exception because national laws apply there.)
So if he is going to travel with you, he can apply for a visa as a dependent of an EU citizen. This visa is free of charge, will be processed quickly, and requires fewer supporting documents. In theory you could also show up with him at a Schengen land border and get a visa there, but doing so will be impractical because airlines will not transport him without a visa.
Him being Iranian or having a Papuan travel document are not obstacle to your right as an EU citizen to travel with your family. It would have to be very specific information in him (or doubts in the validity of the marriage) to deny him a visa.
Your husband can enter Germany with a refugee travel document if:
Source: AufenthV § 18
So, basically you have to check if the travel document allows your husband to reenter Papua New Guinea for at least four months after the planned trip to Germany, as this may be allowed or restricted on an individual basis.
Be aware, that this is the legal situation in Germany and that there may be other restrictions effective in other Schengen countries. Transit through other Schengen countries on your way to Germany or proceeding from Germany to other Schengen countries may be prohibited.
o.m.'s answer is also basically correct (your husband is entitled to a visa since he is married to you as an EU citizen), but I disagree with 'will be processed quickly, and requires fewer supporting documents'. Yes, this may be the wording and intention of the relevant regulation, but depending on where you married, it can turn out to be a quite complex matter to convince a consulate to recognize the authenticity of your marriage.