I'm asking about the cases of 1) converts with no Jewish lineage, or 2) children born to Jewish mothers and Gentile fathers. How is tribal identification for such a person and his descendants determined? Please make sure answers cover both situations.
A person who does not have a Jewish father (whether a convert or a Jew because of the mother) does not belong to any of the twelves tribes. The reason is that tribal membership follows the status of the father. An example is the case of the blasphemer at the end of Parshas Emor (24:10-23) He was the son of an Egyptian man and an Israelite woman of the tribe of Dan. The meforshim state that he attempted to join his mother's tribe and the court rejected his claim. As a result, he blasphemed and was punished.
The point is that a person is a member of a tribe if and only if his mother is Jewish (so that he is Jewish) and his father is a member of one of the twelve tribes.
Additionally, a convert is considered as a "tinok shenolad" (a new born baby). This means that technically he has no relatives. Any relationship restrictions are because of rabbinic law and not from the Torah (such as brother and sister who convert).
We also see this when the Torah deals with the case of a ger who dies with no children to inherit his property.