In order to glean benefits from orthogonal frequency division multiplexing combined with index modulation (OFDM-IM) in the presence of strong Phase-Noise (PHN), in this paper, low-complexity joint PHN estimation and decoding methods are developed in the framework of message passing on a factor graph. Both the Wiener process and the truncated discrete cosine transform (DCT) expansion model are considered for approximating the PHN variation. Then based on these a factor graph is constructed for explicitly representing the joint estimation and detection problem. Taking full account of the sparse and structured a priori information arriving from the soft-in soft-out (SISO) decoder of a turbo receiver, a modified generalized approximate message passing (GAMP) algorithm is invoked for decoupling the frequency-domain symbols. In the decoupling step, mean field (MF) approximation is employed for solving the unknown nonlinear transform matrix problem imposed by PHN. Furthermore, merged belief propagation and MF (BP-MF) methods amalgamated both with sequential and parallel message passing schedules are introduced and compared to the proposed GAMP based algorithms in terms of their bit error ratio (BER) vs. complexity. Our simulation results demonstrate the efficiency of the proposed algorithms in the presence of both perfect and imperfect channel state information.