Note: This does not solve the problem of race conditions.
Create a function that checks whether a room is available based on your conditions and returns a scalar boolean value which can be used in CHECK constraint.
Here you can preview how it works (remember to uncomment the last insert statement):SQL FIDDLE
CREATE FUNCTION is_room_available(int, date)
RETURNS boolean
STABLE
LANGUAGE plpgsql
AS 
$$
BEGIN
  IF EXISTS ( SELECT 1 FROM Accomodation WHERE roomNo = $1 AND $2 BETWEEN arrDt AND depDt ) THEN
    RETURN false;
  END IF;
  RETURN true;
END;
$$;
Create table with new constraint
CREATE TABLE Accomodation (
  roomNo INTEGER NOT NULL,
  arrDt DATE NOT NULL,
  depDt DATE NOT NULL,
  PRIMARY KEY (roomNo, arrDt), 
  CONSTRAINT date_chk CHECK (arrDt<depDt),
  CONSTRAINT room_avail CHECK (is_room_available(roomNo, arrDt)) -- added
  );
Try inserting two rows in separate statements
INSERT INTO Accomodation(roomNo, arrDt, depDt)
VALUES 
(123, to_date('20160202', 'YYYYMMDD'), to_date('20160206','YYYYMMDD'));
INSERT INTO Accomodation(roomNo, arrDt, depDt)
VALUES 
(123, to_date('20160205', 'YYYYMMDD'), to_date('20160208','YYYYMMDD'));
First value is inserted, while when issuing the second insert statement you get a check constraint violation
ERROR: new row for relation "accomodation" violates check constraint "room_avail" Detail: Failing row contains (123, 2016-02-05, 2016-02-08).
Note: This could be easily implemented using triggers as well. You just need to modify the function a little and issue a CREATE TRIGGER statement.