Executar imediatamente com tipo não SQL

Depende do que você quer dizer com 'solução alternativa' O tipo terá que ser declarado no nível SQL, não dentro de um bloco PL/SQL (presumivelmente um pacote neste caso). Isso funcionaria, por exemplo:

CREATE OR REPLACE TYPE t_error_msgs AS TABLE OF VARCHAR2(2000)
/

CREATE OR REPLACE PACKAGE p42 AS
  FUNCTION handler RETURN t_error_msgs;
END p42;
/

CREATE OR REPLACE PACKAGE BODY p42 AS
  FUNCTION handler RETURN t_error_msgs IS
  BEGIN
    RETURN null; -- put real data here, obviously...
  END handler;
END p42;
/

DECLARE
  v_error_msg t_error_msgs;
  v_function varchar2(30);
BEGIN
  v_function := 'p42.handler';
  EXECUTE IMMEDIATE 'BEGIN :result := ' || v_function || '; END;'
    USING OUT v_error_msg;
END;
/

Alternativamente, você pode reconsiderar se realmente precisa que isso seja dinâmico. Presumivelmente, você está passando ou de alguma forma determinando a função a ser chamada em tempo real e preenchendo v_function . Se houver uma lista relativamente curta de valores possíveis, pode ser mais simples ter um case com chamadas de função estáticas individuais.