How to create "auto-increment" field WITHOUT a sequence object?

Hello.

I need to create an auto-increment field on a table WITHOUT using sequences:

CREATE TABLE tbl(
name TEXT,
uniq_id INTEGER
);

Each INSERT to this table must generate a new uniq_id which is distinct from
all others.

The problem is that these INSERTs are rolled back oftenly (i.e. they are
executed within a transaction block which is rolled back time to time), this
is an existing design of the current architecture and unfortunately we have
to live with it. And I need as compact uniq_id generation (with minimum
"holes") as it possible - this is a VERY important requirement (to export
these values into external systems which accepts only IDs limited from 1 to
100000).

So I cannot use sequences: sequence value is obviously not rolled back, so
if I insert nextval(...) as uniq_id, I will have large holes (because of
often transaction rollbacks) and exhaust 100000 uniq_ids very fast. How to
deal with all this without sequences?

I tried

BEGIN;
LOCK TABLE tbl;
INSERT INTO tbl(uniq_id) VALUES((SELECT max(uniq_id) FROM tbl) + 1);
COMMIT;

but seems it performs too hard locking - time to time this query is timed
out (or sometimes deadlocks with other queries).

Is there any other, less hard, locking which allow me to guarantee that no
INSERTs will be performed into tbl between max() calculation and UPDATE
query itself, but does not lock the whole table?