This solution does everything in a trigger, so you can just use a normal INSERT.
For the table itself, we use an autoincrementing ID column:
CREATE TABLE MyTable(ID INTEGER PRIMARY KEY, Name);
We need another table to store an ID temporarily:
CREATE TABLE moriturus(ID INTEGER PRIMARY KEY);
And the trigger:
CREATE TRIGGER MyTable_DeleteAndReorder
AFTER INSERT ON MyTable
FOR EACH ROW
WHEN (SELECT COUNT(*) FROM MyTable) > 100
BEGIN
-- first, select a random record to be deleted, and save its ID
DELETE FROM moriturus;
INSERT INTO moriturus
SELECT ID FROM MyTable
WHERE ID <> NEW.ID
ORDER BY random()
LIMIT 1;
-- then actually delete it
DELETE FROM MyTable
WHERE ID = (SELECT ID
FROM moriturus);
-- then change the just inserted record to have that ID
UPDATE MyTable
SET ID = (SELECT ID
FROM moriturus)
WHERE ID = NEW.ID;
END;