Primary key with randomly varying increments (so it cannot be guessed easily)
I suggest a function taking a regclass parameter that runs ALTER SEQUENCE with a new randomly generated increment before it returns the next value from a given sequence.
Can be used as drop-in replacement for nextval().

Per documentation on ALTER SEQUENCE:


  increment
  
  The clause INCREMENT BY increment is optional. A positive value will
  make an ascending sequence, a negative one a descending sequence. If
  unspecified, the old increment value will be maintained.


However:


  You must own the sequence to use ALTER SEQUENCE.


So we need to take care of privileges. You could make the function SECURITY DEFINER and owned by a superuser. If you don't REVOKE privileges from public it works for anyone on any sequence. There are two basic strategies to restrict usage:


To allow for selected sequences only, change the owner of those sequences to some dedicated role, say randseq and make randseq own the function (still with SECURITY DEFINER).
To allow for selected roles only, REVOKE all privileges on the function from public and GRANT EXECUTE to said roles. You might use a group role to simplify privilege management.


Or combine both:

CREATE OR REPLACE FUNCTION nextval_rand(regclass)
  RETURNS int AS
$func$
BEGIN
EXECUTE format('ALTER SEQUENCE %s INCREMENT %s'
               , $1                          -- regclass automatically sanitized
               , (random() * 100)::int + 1); -- values between 1 and 100
RETURN nextval($1)::int;
END
$func$ LANGUAGE plpgsql SECURITY DEFINER;

-- to restrict usage:
ALTER FUNCTION nextval_rand(regclass) OWNER TO randseq;
REVOKE ALL ON FUNCTION nextval_rand(regclass) FROM public;
GRANT EXECUTE ON FUNCTION nextval_rand(regclass) TO randseq;
GRANT randseq TO ???;

Call:

SELECT nextval_rand('tbl_tbl_id_seq'::regclass);


All you have to do now is replace nextval() with nextval_rand() in the column default of any serial column. And possibly change the owner of the sequence.

ALTER SEQUENCE tbl_tbl_id_seq OWNER TO randseq;
ALTER TABLE tbl ALTER COLUMN tbl_id SET DEFAULT nextval_rand('tbl_tbl_id_seq'::regclass);

Notes

ALTER SEQUENCE is designed not to block concurrent transactions. It takes effect immediately and cannot be rolled back. It should work reliably in a multi-user environment. Read the Notes section of the manual page for the fine print of ALTER SEQUENCE behavior.

There is a very slim chance for a race condition, where two concurrent operations each run ALTER SEQUENCE before calling nextval(). Since we are operating with random numbers anyway, this really doesn't matter.

Since we are running dynamic SQL I would normally SET search_path = public, pg_temp for the function. But since the parameter is regclass, only valid sequence names can be passed and are automatically schema-qualified and escaped unambiguously.