I may have gotten things switched but I seem to recall that Geocities had SSIs before Yahoo took over. But it's stretching my memory to recall it.

How did you have stuff which relies on a server backend (like guestbooks) without having the server inject HTML somehow?

CGI-based images or pages. I don't believe GeoCities let users upload their own CGI scripts, but I believe they had a set of pre-defined CGI tools you could call. You could also set up things like guestbooks using an external service. It wasn't unusual to see "Guestbook provided by $FOO" at the bottom of guestbook pages. Kind of like Disqus, but before JavaScript.

Tripod let people write their own (limited) perl scripts for their site... when I found that out the first thing i did was try to get something from Matt's Script Archive to work, but it didn't. Then I wrote my own guestbook and what had to be the lamest forum ever.

Yes, I remember these external services but in those cases you had to link to a page completely off the site.

Geocities had some feature where you could actually embed guestbook entries into your page.

Truthfully I don't remember for sure, but I used external services just as @Lexarius mentioned. I didn't write it myself at the time.