SuStel:

qaSpa' loS ben before four years ago occurs

I'm slightly confused with this. Shouldn't the {loS ben} as a time
stamp be always the first element in a sentence (i.e. without being
preceded by a verb) ?

This isn't a "time stamp." It's a subordinate clause. The loS ben is the subject of the verb qaSpa'. Remember, ben years ago is a noun in Klingon and may be used as such.

 Could I indeed say the following ?

qaSpa' loS ben, tlhIngan Hol vIghojmoHpu'
I started learning klingon more than four years ago

Yes, though you've got some errors there, and in general I'd expect any such sentence to be reporting the completed event of four years ago occurring.

qaSpu'pa' loS ben, tlhIngan Hol vIghojchoHpu'.
I started to learn Klingon more than four years ago.
Literally, Before four years ago occurred, I started to learn Klingon.

That's not to say qaSpa' always has to have perfective added to it. "Let me take you back in your memory. It's more than four years ago, and..."

-- 
SuStel
http://trimboli.name