Catching errors on Oracle is really, really slow. How about a BEGIN block that attempts to select the record and does this logic in SQL?
DECLARE CURSOR c IS select /*+ FIRST_ROWS */ rowid from Table
WHERE key condition; r ROWID;
BEGIN OPEN c;
FETCH c INTO r;
IF c%NOTFOUND THEN INSERT INTO Table (..Values..)';
ELSE UPDATE Table SET column=? WHERE key=?
END IF;
CLOSE c;
END;
