Was it possible to rename characters in the original NES Final Fantasy?

The text in your screenshot is misleading. What it should say is "in later runs, you should rename them". Once the names had been given, they could not be changed. The AAAA names for all is just default value if no proper names are given. Only thing that giving the AAAA name for the characters does is to allow you to get into the game faster.

In none of the Final Fantasy games can you rename your characters. The name given at the first time is the name you are stuck with.