Respondiendo a tu pregunta, iOS 4 permite que las aplicaciones se ejecuten en segundo plano, pero no funciona igual que en los ordenadores de sobremesa. Las apps que se ejecutan en segundo plano deberían utilizar muy poca memoria y se purgarán en cuanto haya suficientes apps que necesiten la memoria que tienen delante. Así que lo que realmente necesitas es empujar las notificaciones del chat, lo que ayuda a ahorrar la batería del teléfono porque consume menos energía y es manejado por el sistema.
Nimbuz es otra gran opción gratuita que también admite llamadas de voz, muchos mensajes instantáneos, push (por experiencia creo que dura entre 24 horas y 3 días máximo), y solía funcionar incluso con skype voice. ahora no hay ningún cliente de terceros que funcione con skype en absoluto, que yo sepa.
Es mi favorito actualmente y he probado muchas opciones, aunque no he probado Trillian ni Beejive.
Fring es el primero para iPhone y sigue siendo genial también. Cuenta con videollamadas (entre 2 frings). Prefiero Nimbuzz por pequeños detalles, como que fring no muestra de qué protocolo es el perfil específico en la lista.
Al final, la aplicación que elijas será la que mejor se adapte a tu gusto personal, ya que hay un montón de buenas opciones.