In the answer I will use the standard way to number the relators in a presentation. Then, if $G$ is a group of deficiency $\ge 1$ (i.e., admits a presentation with $n$ generators and $k$ relators, where $n>k$) then $G$ is infinite and, moreover, admits an epimorphism to the infinite cyclic group. To prove this, consider the rational vector space $V=Hom(G, {\mathbb Q})$ (where we regard ${\mathbb Q}$ as the additive group of the field ${\mathbb Q}$):
This vector space $V$ is given by imposing $k$ linear equations on
$Hom(F_n, {\mathbb Q})={\mathbb Q}^n$, since every homomorphism to ${\mathbb Q}$ is determined by its values on generators of $G$, while the only restrictions on the images of generators are that each relator maps to zero: Every such condition is one linear equation.
Hence, $dim Hom(G, {\mathbb Q}) \ge n-k\ge 1$. It therefore, follows that there exists a nonzero homomorphism $h: G \to {\mathbb Q}$. The image of this homomorphism is an infinite torsion free finitely generated subgroup (as ${\mathbb Q}$ contains no nonzero finite subgroups), i.e. ${\mathbb Z}^r$ for some $r\ge 1$. Since it is a subgroup of ${\mathbb Q}$, $r=1$. Thus, $G$ admits an epimorphism $h: G\to {\mathbb Z}$, and, hence, is an infinite group. In particular, $G$ contains an element of infinite order (any element $g\in G$ such that $h(g)\ne 0$).
In fact, one can prove more, namely that abelianization of $G$ has rank $\ge n-k$, but we do not need this.
A much more interesting result is due to Baumslag and Pride: They proved that every group of deficiency $\ge 2$ has a finite index subgroup which admits an epimorphism to a nonabelan free group. Such a group is called large. See also http://arxiv.org/pdf/1007.1489.pdf and references there.
If the group $H = \langle S \cup \{t\} \mid R \cup \{tat^{-1}=\theta(a) : a \in A\})$ was finitely presented, then it would be presented using a finite subset of the relation set in the infinite presentation. That is, we would have $H = \langle S \cup \{t\} \mid R \cup \{tat^{-1}=\theta(a) : a \in X\})$ for some finite subset $X$ of $A$.
But this presents the group $G_{*B}$, where $B = \langle X \rangle$. So if $A$ is not finitely generated, then $B$ is a proper subgroup of $A$.
But then, by Britton's Lemma on HNN extensions, if we choose $a \in A \setminus B$, then the element $tat^{-1}\theta(a)^{-1}$ of $G_{*B}$ contains no pinch, and so is not equal to the identity. But it is equal to the identity in $G_{*A}$, contradiction.
Best Answer
In fact, in this case you can determine the group! Finiteness is absolutely crucial here, however.
Let's say our generators are $a_1,...,a_n$, our relators are $R_1,...,R_m$, and every element of our group is represented by a word of length $\le l$. Then any word of length $l+1$ can be transformed into a word of length $\le l$ by applying an appropriate (perhaps extremely long) sequence of relations. Once we see this phenomenon we know we've found all the elements of the group. Since for any $l$ there are only finitely many words of length $l+1$, via appropriate brute-force search we can eventually find and recognize such an $l$ if it exists, so there's no need for us to be given an upper bound on the lengths of the words at the outset. (Of course the first such $l$ we find might not be the smallest such $l$, since by using longer sequences of relations it may turn out that a shorter value of $l$ would have sufficed, but that's fine.)
Once we have found such a sufficiently large $l$, we can just try to greedily build the multiplication table (my original idea with graphs did not work, as pointed out by Eric Wofsey and Adayah below). At any given stage, we'll have a guess at an equivalence relation on the set $L$ of words of length $\le 2l$. At each stage we check whether the multiplication/inverse tables this equivalence relation generates on the set of words of length $\le l$ (we need to go up to length $2l$ to deal with multiplications) satisfies the group axioms and our relations; if it doesn't, then we add the appropriate pairs to our equivalence relation and rinse-and-repeat. Eventually we wind up with the smallest equivalence relation which satisfies our constraints, which gives our group.
Note that nothing here relies on groups per se; the same basic idea would work for any sort of algebraic structure.