Will this still have the same meaning if it were "Nyerere alikuwa rais wa Tanzania wa kwanza"?
I think so - grammatically, it can't really mean anything else because the wa makes it clear that it refers back to rais and not to Tanzania - but I'm not sure about how natural it is.