Rather than an answer, this is more of an anti-answer: I'll try to persuade you that you probably don't want to know the answer to your question.
Instead of some exotic nonalgebraic Lie algebra, let's start with the one-dimensional Lie algebra $\mathfrak{g}$ over a field $k$. A representation of $\mathfrak{g}$ is just a finite-dimensional vector space + an endomorphism. I don't know what the affine group scheme attached to this Tannakian category is, but thanks to a 1954 paper of Iwahori, I can tell you that its Lie algebra can be identified with the set of pairs $(\mathfrak{g},c)$ where $\mathfrak{g}$ is a homomorphism of abelian groups $k\to k$ and $c$ is an element of $k$. So if $k$ is big, this is huge; in particular, you don't get an algebraic group. (Added: $k$ is algebraically closed.)
By contrast, the affine group scheme attached to the category of representations of a semisimple Lie algebra $\mathfrak{g}$ in characteristic zero is the simply connected algebraic group with Lie algebra $\mathfrak{g}$.
In summary: this game works beautifully for semisimple Lie algebras (in characteristic zero), but otherwise appears to be a big mess. See arXiv:0705.1348 for a few more details.
(Edited to correct mistakes signaled in comments below).
I don't know much about the first steps on the theory, Krein and Tannaka.
I can just say their works answer a question that seems very natural now,
and that I think was natural even then. Since the beginning of the 20th century, representations of groups had been studied, used in many part of mathematics (from Number Theory, think of Artin's L-function to mathematical physics) and more and more emphasized as an invaluable tool to study the group themselves. It was therefore natural to see if a group (compact say) was determined by its representations.
But then, I want to insist on the fundamental role played by Grothendieck in the development of the theory. This role comes in two steps. First Grothendieck developed a pretty complete end extremely elegant theory for a different but analog problem: the problem of determining a group (profinite say) by its category of sets on which it operates continuously. It is what is called "Grothendieck Galois Theory", for Grothendieck did that in the intention of reformulating and generalizing Galois theory, in a way that would contain his theory of the etale fundamental groups of schemes. What Grothendieck did, roughly, was to define an abstract notion of Galois Category. Those categories admit special functors to the category of Finite Sets, called Fibre Functors. Grothendieck proved that those functors are all equivalent and that a Galois category is equivalent to the category of finite sets with G-action, where G is the group of automorphism of a fibre functor. He then goes on in establishing an equivalence of categories between profinite groups and Galois categories, with a dictionary translating the most important properties of objects and morphisms on each side. This was done in about 1960, and you can still read it in the remarkable original reference, SGA I.
Already at this time, according to his memoir Recoltes et Semailles, Grothendieck was aware of Krein and Tannaka's work, and interested in the common generalization of it and his own to what would become Tannakian category, that is the study of categories that "look like" categories of representations over a field $k$ of a group,
As he had many other things on his plate, he didn't work on it immediately, but after a little while gave it to do to a student of him, Saavedra. As Grothendieck was aware, the theory is much more difficult than the theory of Galois categories. Saavedra seems to have struggled a lot
with this material, as would have probably done 99.9% of us. He finally defended in 1972, two years after Gothendieck left IHES, and at a time he was occupied by other, in part non-mathematical subject of interest. Saavedra defined a notion of Tannakian category (as a rigid $k$-linear tensor category with a fibre functor to the category of $k'$-vector space, $k'$ being a finite extension of $k$) but he forgot one important condition (then $End(1)=k$) and some of the important
theorems he states are false without this condition.
After that, mathematics continued its development and Tannakian categories began to sprout up like mushrooms (e.g. motives (69, more or less forgotten until the end of the 70's), the dreamt-of Tannakian category of automorphic representations of Langlands (79), to name two extremely important in number theory). Then Milne and Deligne discovered in 1981 the mistake mentioned above in Saavedra's thesis, gave a corrected definition of Tannakian'a category, and were able to prove the desired theorems in the so-called neutral case, when $k'=k$ (I believe with arguments essentially present in Saavedra). Later with serious efforts, Deligne proved those theorems in the general case. Modern theory have added many layers of abstraction on that.
Best Answer
$\DeclareMathOperator\Rep{Rep}\DeclareMathOperator\Vect{Vect}\DeclareMathOperator\Aut{Aut}\DeclareMathOperator\Mod{Mod}\DeclareMathOperator\GL{GL}\DeclareMathOperator\Hom{Hom}$The infinitude of the input data is deceptive. For example, an infinite finitely presented group may appear to be infinite input data but it's fully specified by a finite alphabet and a finite set of words in it. The same sort of thing happens here; everything is "finitely presented" in a suitable sense.
First, let's recall the statement of Tannaka-Krein duality here so we can see exactly how the group arises. Let $G$ be a finite group and let $\Rep(G)$ be its category of representations (say over $\mathbb{C}$). $\Rep(G)$ is equipped with a monoidal structure in the form of the tensor product of representations and with a forgetful functor $F : \Rep(G) \to \Vect$. We are interested in studying natural automorphisms $\eta : F \to F$ compatible with the tensor product in the sense that the obvious diagram (which can be found on page 8 of Commelin - Tannaka duality for finite groups for completeness) commutes. Every element of $G$ gives an element of this group of natural automorphisms, which we'll denote $\Aut^{\otimes}(F)$.
So our reconstruction begins first with the group $\Aut(F)$ of natural automorphisms of $F$, then cuts out a subgroup satisfying some extra compatibility conditions. Let's start with figuring out what data we need to describe $\Aut(F)$.
Explicitly, an element of $\Aut(F)$ is a family $\eta_V : F(V) \to F(V)$ of automorphisms of the underlying vector spaces of all representations of $G$ which is compatible with all morphisms between representations. There is a universal such representation generated by a single element, namely $\mathbb{C}[G]$ regarded as a representation via left multiplication, and compatibility with all morphisms $\mathbb{C}[G] \to V$ implies that any such natural transformation $\eta$ is completely determined by what it does to $\mathbb{C}[G]$. On $\mathbb{C}[G]$ any such natural transformation needs to be compatible with right multiplication, and so must be left multiplication by some invertible element of $\mathbb{C}[G]$. Conversely any such element gives an element of $\Aut(F)$. Hence
$$\Aut(F) \cong \mathbb{C}[G]^{\times} \cong \prod_i \GL(V_i)$$
where the $V_i$ are the irreducible representations of $G$. (Secretly we are using the Yoneda lemma but I wanted to be completely explicit.) This reflects the fact that the data of the category and the fiber functor is equivalent to the data of the number and dimensions of the irreducible representations respectively. So we can use these as our initial data:
This step of the reconstruction reflects a more general fact, namely that if $R$ is a $k$-algebra, $\Mod(R)$ the category of left $R$-modules, and $F : \Mod(R) \to \Vect$ the forgetful functor, then the natural endomorphisms of $F$ are canonically isomorphic to $R$ (as a $k$-algebra), which again follows from the Yoneda lemma.
The tricky part is how to describe the influence of the tensor product. Explicitly, let $\eta : F \to F$ be an element of $\Aut(F)$ again. Then there are two ways to use $\eta$ to write down an automorphism of the underlying vector space of a tensor product $F(V \otimes W)$:
$\eta$ lies in $\Aut^{\otimes}(F)$ if and only if these are equal. More explicitly, if $\eta$ is left multiplication by some element $\sum c_g g \in \mathbb{C}[G]$, then the first map is
$$\left( \sum c_g \rho_V(g) \right) \otimes \left( \sum c_g \rho_W(g) \right)$$
while the second map is
$$\sum c_g \rho_V(g) \otimes \rho_W(g)$$
and setting $V = W = \mathbb{C}[G]$ and comparing coefficients shows that these can't be equal unless $\sum c_g g = g$ for some $g$.
So how do we describe this restriction to a computer? The key point is that since everything in sight is compatible with direct sums it suffices to restrict our attention to the irreducible representations $V_i$, so we only need to compare the maps $\eta_{V_i} \otimes \eta_{V_j}$ and $\eta_{V_i \otimes V_j}$ for all $i, j$. This means that we need to describe
This requires that we know first of all the decompositions
$$V_i \otimes V_j \cong \bigoplus_k m_{ijk} V_k$$
of the tensor products of the irreducibles into irreducibles. So this is our third piece of data:
These multiplicities are equivalent to the data of the character table of $G$, and in particular it is possible to compute Data 1, 2 from this data, so in some sense Data 1, 2 are redundant. But we already know that the character table is not enough. The multiplicities only tell us about $\eta_{V_i \otimes V_j}$, but not about $\eta_{V_i} \otimes \eta_{V_j}$.
To get our last piece of data, let's think about how a computer would represent $\eta$. Specifying linear transformations $\eta_{V_i} \in \GL(V_i)$ requires writing down a basis of each $V_i$. These bases give rise to two different bases of the tensor products $V_i \otimes V_j$: on the one hand the tensor product basis, and on the other hand the basis coming from the decomposition into irreducibles $\bigoplus_k m_{ijk} V_k$. So the final piece of data we need is the identification between these:
(This is essentially the data of the identifications $F(V \otimes W) \cong F(V) \otimes F(W)$ making $F$ a tensor functor: unlike in the case of maps between monoids, being a tensor functor is a structure, not a property, because these maps are required to satisfy coherence conditions.)
This is the data we need to write $\eta_{V_i} \otimes \eta_{V_j}$ and $\eta_{V_i \otimes V_j}$ as matrices with respect to the same basis. These transition matrices should be definable over a splitting field of $G$ at worst, so this really is finite data.
Edit, 12/26/21: Wow, sorry everyone, there's actually a small gap here that needs to be fixed. The "decomposition basis" I described above is not well-defined because the decomposition of $V_i \otimes V_j$ into irreducibles isn't unique when the multiplicities are greater than $1$! Instead we need to proceed as follows: the truly fully canonical decomposition into irreducibles takes the form
$$V_i \otimes V_j \cong \bigoplus_k \text{Hom}_G(V_k, V_i \otimes V_j) \otimes V_k$$
where the tensor product on the RHS is just the ordinary tensor product of vector spaces. To get a decomposition basis as claimed above we need to make additional choices, namely a choice of basis for each homspace $\Hom_G(V_k, V_i \otimes V_j)$. I don't think this choice really ends up mattering but I think it does still need to be made? Maybe a slightly nicer approach could avoid it.