I can’t really add a lot more to coldcoffee’s reply, except applying for a TARC doesn’t really have anything to do with getting work sponsorship–it’s a complicated process no matter what. Also, AFTER you have a TARC, you CAN apply for a work permit and work without sponsorship–you do not need to live with a blood relative.
As coldcoffee said, enter Taiwan on your ROC passport, then go to the immigration agency to start the process. (Don’t waste time with this–the entry/exit permit is valid for just 90 days, I believe.) Take all the documents you can, including your father’s official documents (including passport, Taiwan ID, and death certificate, notarized and authenticated, just in case). You will probably need your parents’ marriage certificate, notarized and authenticated, also.
You WILL need to find someone who will let you register at their hukou, but this can be any friend, or relative, or even a landlord (it just has to be someone who has property in Taiwan).
If you have an ROC passport, it means you are in the system somehow, so even if your father did not register you at his hukou, at some point, you were recognized as his child. I’m pretty sure it will be possible for you to get the TARC, it’s just a question of producing the correct documents and being very, very patient and persistent.
Here is an earlier thread that details the TARC application process. It will give you a better idea of how the process works. 29 year old Hapa with Taiwanese Mom claiming Citizenship
Good luck.