Also ich benutze K9 mit gmx freemail und imap ohne Probleme.

Bei der gms App müsste es eigentlich reichen, dass Du Dich mit eMail und Passwort anmeldest und es richtet es Dir automatisch ein.
Hast Du die richtige gmx App runtergeladen. Da gibt's nämlich auch so ne komische gmx sms app.
Ich meine diese hier:
GMX Mail - Android Apps und Tests - AndroidPIT

Bezüglich imap: Es ist eigentlich kostenpflichtig, stimmt. Aber seitdem gmx ihr eigenes App auf den Markt gebracht haben, funktioniert es auch mit freemail. Also ich hab nur ne freemail und kann's nutzen.

EDIT:

Hier mal ne Schritt für Schritt Anleitung für K9 (Hab mein Handy auf englisch, dürfte aber nicht schwer sein zu verstehen, was gemeint ist):

1. Acount hinzufügen
2. vollständige eMail (mit @gmx.de) und Passwort eintragen
3. Manuel Setup anklicken
4. imap auswählen
5. - Unter Benutzername ist nun nur der Name (ohne @gmx.de), da @gmx.de ergänzen
- unter imap server: imap.gmx.de eintragen
- Security Type habe ich "always ssl" gewählt
- port stellt sich automatisch ein (993)
- dann auf weiter drücken
6. nun müsste ein Posteingangsservertest starten und funktionieren
7. - nun wird der Postausgangsserver eingestellt
- hier müsste unter smtp server: mail.gmx.de stehen
- security type wieder: SSL (always)
- Port 465
- Haken bei: require sign-in
- auf weiter drücken
- nun müsste ein positiver Posteingangsservertest laufen
8. - Folder Poll Frequency: habe ich auf niemals, da durch push die Nachrichten sowieso kommen und kein poll spart Batterie.
- Haken bei Enable push mail for this account
und den Rest einstellen wie Du magst.
Auf weiter klicken und der Account ist eingestellt.
Im letzten Fenster kannst Du einen Namen für den account (nur für dich in der K9 App) und einen Absendernamen (sehen dann die Empfänger) eingeben.

Fertig

Hab eben so einen Account für dieses Tutorial eingerichtet und funktioniert.