Semi-academic job: techniques to apply
First a remark: you don't seem to even consider postdoc positions, is this a choice? These are research positions of course, but this is by far the most common way for a recent PhD graduate to start an academic career, possibly applying for assistant professor positions later on if this is something that you consider doing.

As far as I know, what you are looking for is called (full-time) lecturer position in the British Isles academic system (I'm in Ireland myself). These positions are not very common but I've seen a few being advertised from time to time, that could depend on the institution. They are probably a bit competitive (though less than assistant professor jobs), so you might need to strengthen your teaching record first. For that the best way is to contact every department you know asking them if they have any short-term teaching needs paid by the hour that you could fill. In my experience it's quite common for CS departments to be under-staffed so there's a decent chance you'll find something.