There is a metis USE flag for buildling taucs with/without METIS support but building without simply doesn't work. The Makefiles try to link against libmetis regardless but even when this is fixed, there is an unresolved reference to the METIS_NodeND function. Maybe this could be fixed with a patch but I don't know anything about either package.
Thanks for the report. sci-libs/metis is now a mandatory dependency.