"Stein-" ist hier ein (salopp) emotional verstärkendes Präfix.
Spätmittelhochdeutsch steinrīche: reich an Edelsteinen, sehr/ungewöhnlich reich.
(Duden)
Jedoch steht im Wörterbuch der Gebrüder Grimm unter steinreich:
oft falsch erklärt: 'reich an edelsteinen'
[...]
richtige erklärung schon bei Adelung 'sehr reich ..., von stein, sofern es oft eine intension bezeichnet'
Sofern ich mich nicht irre, soll von Stein hier das Reichwerden durch den Abbau von/Handel mit Stein bezeichnen. Bei Grimm ist eine Gegend bzw. eine Krone reich an (Edel-)steinen, also steinreich. Bei Dudens Eintrag stellt sich die Frage, ob man einen Menschen auch als reich an Edelsteinen bezeichnen kann (-reich bedeutet durch viel von etwas gekennzeichnet). Meinem Sprachgefühl nach geht das nicht, und Adelungs Erklärung wird von der schon immer dagewesenen Teure von Stein als Baumaterial gestützt. Siehe dazu noch die letzte Seite dieses PDF.
Laut http://www.dwds.de/?qu=stein- ist steinreich seit dem 15. Jahrhundert belegt. Das deckt sich mit der Einordnung ins Spätmittelhochdeutsche von Duden.
Steinalt scheint auch den bei Grimm angeführten Beispielen zufolge etwas älter zu sein (16. Jh.).
Älter als steinreich ist jedoch steinhart (mhd.). Obwohl ich bei weitem kein Adelung bin, stelle ich eine weitere Möglichkeit in den Raum, parallel zur Entwicklung von beispielsweise ur:
uralt → sehr alt → sehr hart → ur hart
steinhart → sehr hart → sehr reich → steinreich