You are right that are examples of RNA that functions as a catalyst, e.g. inside the ribosomes and in the spliceosome.
While the known functions of catalytic RNA are indeed, as you say, ubiquitous, very important and they certainly were already present in the last common ancestor of all present cellular living beings, none of those functions are likely to be so ancient as to have existed in the first life forms.
The nucleotides that compose a RNA molecule do not have chemical properties that are different enough to allow RNA to have a versatility comparable with the peptides/proteins, which can be used to make catalysts for a much wider range of chemical reactions and which can be attached to membranes for some of the most important functions, e.g. for ionic pumps.
While the number of amino-acids must have been much smaller in the beginning, it is likely that about 6 were already in use, i.e. alanine, a hydrophobic (valine), an acid (aspartic), an alcohol (serine) and 2 with unusual forms (glycine and proline) that can determine how the peptide will coil and fold.
The variety of amino-acid properties, even in the minimal set, allows the implementation of much more functions than can be imagined for RNA.
I am not aware of an example of a catalytically active polypeptide which is assembled without any RNA template, but that is not very relevant, because there is no doubt that, after the appearance of the transcription of RNA into proteins, most non-ribosomal peptides must have been replaced by more complex proteins, which were able to perform a more specific and faster catalysis.
I do not agree that "what’s necessary is some kind of structure that records bits of information in some kind of order".
On the contrary, this is what is impossible to have existed and it is the main reason why RNA must have been a later invention, after self-replicating life forms already existed for a long time.
What I say here about RNA, is valid for any other kind of molecular memory, so it is unlikely that any other polymer was used before RNA, as in some hypotheses.
Any other function of RNA besides the self replication of the RNA molecule must have appeared only much later, after a long evolution of RNA.
The reason is that even if any kind of useful RNA molecule, e.g. a catalytic ribozyme, ever appeared earlier, it disappeared without descendents, because it was not replicated.
So, if the RNA replication was the first function, that requires both the presence of ATP and of the other nucleotides and of some macromolecule that will catch the nucleotides and link them into the RNA molecule, using as a template the RNA that is replicated.
Even if we assume that the actual catalyst of the RNA replication was also a RNA molecule, that leaves open the source of the component nucleotides.
There must have already existed a catalytic system that transformed the simple precursors from the environment into ATP and other nucleotides through a long chain of reactions.
There exists no other better hypothesis for the nature of those catalysts than that they were non-ribosomal peptides resembling the active segments of the present-day enzymes that are used for those reactions.
Like I have already said, it is a logical impossibility for any kind of information-recording molecular memory to have existed since the beginning.
The way how the still existing non-ribosomal peptides are assembled in the correct sequence in the present-day organisms is not known well. Also the way how membranes are assembled is not known well. We have much less information about these than about nucleic acid replication and protein synthesis, for which a large number of investigative tools have been developed.
In any case, it is possible to imagine (and I believe that the attempt to design such a system would be a worthy research subject) a self-replicating system without any molecular memory, where some kind of peptides directed the assembling of another kind of peptides, which directed the assembling of another kind of peptides and so on for several steps, until the cycle was closed and the last kind of peptides directed the assembling of the first kind.
Of course, that must not have been just a simple cycle but a network of reactions, to generate all the components of the life form, but the network of reactions must have included all the cycles required to ensure that the complete replication of the life form is done.
In conclusion, you are right about "how important this information storage requirement is for evolution" and I have already written in a previous post that the evolution of the complex living beings of today could not have happened without the invention of a molecular memory.
Nevertheless, it is impossible for any such information storage mechanism to have already existed since the origin of life.