Hallo,
Nur mit JavaScript, du musst ja das DOM ändern.
nur auf reine JavaScript Lösung möchte ich ungern setzten denn zum einen habe ich davon nur sehr wenig Ahnung und zum anderen muss ich rechnen dass JavaScript deaktiviert sein könnte. OK hier handelt sich sich um eine Spielerei, wer also JavaScript deaktiviert hat, würde den Effekt eben nicht sehen.
Was du machen kannst, um JS zu vermeiden, ist, einen von den FontAwesome-Vorgaben unabhängigen Klassennamen zu wählen, das Icon darüber einzubinden und bei :hover ein anderes Icon anzuzeigen.
Wäre es dann vielleicht nicht doch sinnvoll mein HTML umzubauen bevor ich Anfange zu tricksen?