Want to delete then insert with single statement using a CTE in Postgres
Without a UNIQUE constraint standing in the way, your original query works just fine. See below.
I would throw in a separate CTE to provide all input values once:
WITH input(a, b, c) AS (VALUES ('abc', 2, 'new value'))  -- provide values once
   , del AS (
   DELETE FROM foo AS f
   USING  input i
   WHERE  f.a = i.a
   AND    f.b = i.b
   )
INSERT INTO foo (a, b, c)
TABLE input;

The DELETE cannot delete rows from the INSERT in the same statement, as both see the same snapshot of underlying tables. Meaning, the DELETE cannot see the rows entered by the INSERT in the other CTE. Both are executed at the same time, virtually. Related:

Why can&#39;t rows inserted in a CTE be updated in the same statement?

That's also the reason why this cannot work with a UNIQUE index on (a.b). Uniqueness is enforced at all times. The INSERT still sees rows being deleted in the other CTE. The obvious alternative would be an UPSERT. But that cannot be the case, since you mentioned that there is no PK and the DELETE can delete 0-n rows.
As a_horse commented: would work with a deferrable constraint, though. See:

Constraint defined DEFERRABLE INITIALLY IMMEDIATE is still DEFERRED?

But deferrable constraints are considerably more expensive and don't work with FK constraints, nor as arbiter in UPSERT statements ...
Note that a free-standing VALUES expression may require explicit type casts. See:

Casting NULL type when updating multiple rows

Related:

How to use RETURNING with ON CONFLICT in PostgreSQL?


That said, I don't see how this is superior to a DELETE and a separate INSERT in a single transaction - which also works with UNIQUE constraints. You commented:

It's a lot easier to use db parameters with a single statement and our db library.

If the statement is used a lot, consider a function:
CREATE OR REPLACE FUNCTION f_foo_delins(_a text, _b int, _c text)  -- actual types
  RETURNS void LANGUAGE sql AS
$func$
   DELETE FROM foo
   WHERE  a = _a
   AND    b = _b;

   INSERT INTO foo ( a,  b,  c)
   VALUES          (_a, _b, _c);
$func$;

Then the call is simple:
SELECT f_foo_delins('abc', 3, 'new value');

If you only need it for some sessions, a temporary function might be an option. See:

How to create a temporary function in PostgreSQL?

Or a prepared statement with the above CTE:
PREPARE foo_delins(text, int, text) AS
WITH del AS (
   DELETE FROM foo
   WHERE  a = $1
   AND    b = $2
  )
INSERT INTO foo ( a,  b,  c)
VALUES          ($1, $2, $3);

Call:
EXECUTE foo_delins('abc', 4, 'new value');

Most languages have their own implementation of prepared statements using libpq ...
Prepared statement and function know their input types. Explicit type casts are not required (except special cases).
Related:

What is the difference between prepared statements and SQL or PL/pgSQL functions, in terms of their purpose?