You don't even understand. The methane's mostly for the hydrogen, used to make ammonia or some other nitrogen compound. There are other ways of making this, Birkeland Eyde, for instance, but there like one third as efficient, at best. This means people starve. You might make the case that we could efficiently use livestock manure as a substitute (it's the green solution), but not if you're going to turn this into Planet Vegan. Given the necessity of animal manure, it's difficult to think that "get rid of all the livestock" stems from anything other than bizarre vegan tendencies.
If you absolutely have to get rid of the livestock, so be it, but then you really do need the fossil fuels. Pick, it's one or the other as far as I can tell.
> And there are natural fertilizer paths that aren't cattle.
Nope. You've got livestock (hogs, poultry, etc), or you've got fossil-fuel-based Haber-Bosch. I'm not even really aware of any science fiction concepts "other paths".