Usar COUNT(*) está OK se você também usar rownum=1:
declare
l_cnt integer;
begin
select count(*)
into l_cnt
from x
where x.col_a = value_a
and x.col_b = value_b
and rownum = 1;
end;
Isso sempre retornará uma linha, portanto, não há necessidade de manipular nenhuma exceção NO_DATA_FOUND. O valor de l_cnt será 0 (sem linhas) ou 1 (existe pelo menos 1 linha).
