Have you tried copying the Mountain Lion version of Messages into your new installation? If you allowed Time Machine to backup your Applications folder you ought to be able to get it fairly easily, just give a new name like "Messages ML" or such.
If you don't have it in a backup, then you may be able to extract it from the Mountain Lion installer using
Pacifist. Just right click the installer and choosing "Show Package Contents", then open Contents/SharedSupport (iirc) and there should be an OSInstall.mpkg in there, just open it in Pacifist and Messages.app should be in one of the essentials packages for you to copy out; again make sure you rename it rather than replacing the Mavericks one, in case it doesn't work.
Just as a possible step before the complete downgrade option
You'll also want to leave some
OS X Feedback; I dunno how much impact it really has, but if enough people complain about a lost feature then Apple may bring it back in some way, especially if you mention you'd love it on iOS too, they won't be able to resist!