New as in not of the old creature but now of the new creature. "you are a new creation" as opposed to the old.
That is the old songs that you sung in the bar were drunk songs about capping people and raping your ho (is that the right spelling) [NOTE: I hope no one did that but those are the worldly songs of today], but sing a new song. Song of redemption of the redeemer. That's typically how "new song" is interpreted. Same argument as for the defining of "all". All means all right except when it doesn't mean literally all everywhere at all times. It means all Jews, etc. The context determines the meaning of the word.
Psa 40:1 To the chief Musician, A Psalm of David. I waited patiently for the LORD; and he inclined unto me, and heard my cry.
Psa 40:2 He brought me up also out of an horrible pit, out of the miry clay, and set my feet upon a rock, and established my goings.
Psa 40:3 And he hath put a new song in my mouth, even praise unto our God: many shall see it, and fear, and shall trust in the LORD.
Here's an example of that in the context of salvation/deliverance, and here it isn't compose a new song, but the Lord put a new song in my mouth. Many times in the Psalms "new song" is found in the context of salvation.
In Rev. 14 they sang a new song of which the REDEEMED 144,000 alone could learn -- "which were redeemed from the earth". Context is King!
Nowhere is there a command to compose a new song, when new song is used where scripture is most clear that new song was put in the mouth of those who sang by the Lord.