Yeah it is written like that to be polite to god-haters, but the truth is that if you accept that you can be a paladin without serving a deity, you basically admit that the portfolio system is nonsense and you can just pull magic out of your behind just because.
Also if Tyr died, another deity would rise to take his place and porfolio (this actually happened, Tyr did die and gave all his power and portfolios to Torm). A paladin devoted to Tyr would probably get a chance to accept Torm (whose portfolio included "paladins") or serve him by proxy of serving justice.
You can't really get around this without breaking the lore tbh.
