Actually, "I became a big fan of his" is natural, and it is known as a double possessive. It has been idiomatic in English for decades.
Keep in mind that it is only used when the second part is a person, you wouldn't say "I'm a frequent visitor if the museum's".
However, you should avoid double possessives in official documents.