Not sure if is going to allow you to enter recovery mode without an hdd
Btw, what they have said is right, your PS3 is fine (good news) because you can see the error message when you boot without hdd
The next thing you need to decide is if you want to try to recover the files from that hdd, for that you need the EID root key + a PC
This could allow to recover some files incase the PC program is able to access the filesystem... but the recovered files could be corrupt, so incase of recovering file from a damaged hdd like this i suggest to do it ONLY with worthy files... thats savegames mostly (and trophies incase you are not connected online), but thats all... dont try to recover games or stuff like that because are big files and the probability of them to be corrupted is higher (and is going to be lot harder to know which ones are corrupted)
The next decission you need to take is if you are going to run some scan tests in that hdd to try to continue using it.... or you are going to replace it by a new hdd
The scans are good to do anyway, because maybe the hdd is fine. What you have damaged is the filesystems (thats for sure), but the hdd is unknown
But you need a PC for that... you mentioned you have an "all-in-one" computer... not sure what is that

can you mention the brand-model ?... it runs windows ?, and it have a SATA hdd ?
You could do it with a laptop/netbook, you need to remove the hdd (with windows installed), and connect the PS3 hdd, then you need to boot from a "liveCD" (or liveUSB) as @"Chaos Husky" mentioned
There are some ISOs freely availables with hdd tools... my favourite is
MHDD btw
Basically, you need to do a "surface scan"... it takes lot of time, it reads the data from all sectors and messures the times needed to read that data... then it shows a checkered pattern and some counters where you can see if how many sectors you have with problems and his exact positions
If you pass that "surface scan" test and it reports 0 critical problems... it means your hdd is perfect