Hard problem with concurrency

OK, this is the problem:

I want to write a bit of SQL that if a row exists in a table, then update
it, otherwise it will update it. Problem is, there is a very high chance of
simultaneous execute of this query on the same row (the rows have a unique
index).

So, strategy one:

begin;
update row;
if (no rows affected) insert row;
commit;

Problem - race condition! If the two transactions run at the same time, the
second will end up doing an insert on a unique row which will cause query
failure

Strategy two:

begin;
select row for update;
if (row returned) update;
else insert;
commit;

Problem - race condition. The row-level locking doesn't allow me to lock
'potential rows', so if the row does not yet exists and two transactions run
simultaneously then the second with die with a unique violation;

Strategy three:

begin;
lock table in exclusive mode;
update row;
if (no rows affected) insert row;
commit;

Problem - Works, but this table needs high concurrency. Every time a member
hits a page of the site that needs authentication, this function is called.
In particular, the login transaction can take a little time sometimes and we
can't halt everyone else's activites for that duration...

So what is the solution???

I'm not sure if acquiring a ROW EXCLUSIVE MODE lock will help at all. Also,
I can't try the insert and then the update because the INSERT, in Postgres,
will cause an outright transaction failure.

What the heck is the solution??

Chris