I know what the dual of a vector means (as a map to its field), and I am also aware of of the definition a dual of a tensor as,
$$F^{*ij} = \frac{1}{2} \epsilon^{ijkl} F_{kl}\tag{1}$$
I just don't understand how to connect this to the definition of the dual of a vector. Or are they entirely different concepts? If they are different then why use the word dual for it?
I know this is kind of mathematical or may be a stupid question, but I have a problem with understanding the need for dual of Dual Field strength Tensor in relativistic ED. I mean you could say that I am going to define another tensor using eq. (1) call it whatever we like.
The dual of a tensor you refer to is the Hodge dual, and has nothing to do with the dual of a vector. The word "dual" is used in too many different contexts, and in this case it is even used the same $*$ symbol. One usually specifies "Hodge dual", or "Hodge star operator", to avoid confusion. Both these "duals" are isomorphisms between vector spaces endowed with inner product.
The dual of a vector space $V$ is the vector space $V^*$ consisting in the linear functions (functionals) $f:V\to \mathbb R$ (or $\mathbb C$ if $V$ is a complex vector space). The dual of a vector $v\in V$ makes sense only if $V$ is endowed with an inner product $g$, and it is defined as $v^\flat\in V^*$, $v^\flat(u)=g(v,u)$. This dual is an isomorphism between the inner product vector space $(V,g_{ab})$ and its dual $(V^*,g^{ab})$.
The Hodge dual is defined on totally antisymmetric tensors from $\otimes^k V$, that is, on $\wedge V^k$. It is defined on $\wedge V\to \wedge V$, where $\wedge V=\oplus_{k=0}^n\wedge^k V$. It also requires the existence of an inner product $g$ on $V$. The inner product extends canonically to the entire $\wedge V$.
The Hodge dual is defined as follows. We construct a basis on $V$, which is orthonormal with respect to the inner product $g$, say $e_1,\ldots,e_n$. Then, for each $k$, there is a basis of $\wedge^k V$ of the form $e_{i_1}\wedge\ldots \wedge e_{ik}$. This basis is considered to be orthonormal too, and by this, $g$ defines an inner product on $\wedge^kV$.
The Hodge dual is defined first between $\wedge^kV\to\wedge^{n-k}V$, Both spaces have the same dimension, which is $C^k_n$. The canonical isomorphism between them is defined first on the elements of the basis:
$$*(e_{i_1}\wedge\ldots\wedge e_{i_k})=\epsilon e_{j_i}\wedge\ldots\wedge e_{j_{n-k}}.$$ Here, the indices $i_1,\ldots,i_k,j_1\ldots j_{n-k}$ are a permutation of the numbers between $1$ and $n$. $\epsilon$ is $+1$ if the permutation $i_1,\ldots,i_k,j_1\ldots j_{n-k}$ is even, and $-1$ otherwise. This defines uniquely the isomporphism. It extends uniquely to $\wedge V=\oplus_{k=0}^n\wedge^k V$, since this is a direct sum of vector spaces.
Please note that the vectors also admit Hodge duals, but their duals are elements of $\wedge^{n-1}V$.
Since we can consider that $\mathbb R=\wedge^0 V$, the Hodge dual of the scalar $1$ is the volume element $*1:=e_1\wedge\ldots\wedge e_n\in\wedge^n V$. In a basis, it is denoted by $\epsilon_{12\ldots n}$.
Similarly, the Hodge dual can be defined on the space of exterior forms $\wedge V^*$.
In the case of Lorentzian spacetimes of dimension $4$, the Hodge duality establishes isomorphisms between $\mathbb R$ and $\wedge^4 V$, between $V$ and $\wedge^3 V$, and between $\wedge V^2$ and itself.
An alternative way to construct the Hodge duality is for the Clifford algebra associated to $V$. In this case, there is an isomorphism (as vector spaces with inner product) between $\wedge V$ and $Cl(V)$. The Hodge dual translated to the Clifford algebra language as Clifford multiplication with the $n$-vector which corresponds to the volume element, $\gamma_1\cdot\gamma_2\cdot\ldots\cdot\gamma_n$.
Back to the confusion of terminology. For a vector $v\in V$, the dual is a covector $v^\flat\in V^*$. The Hodge dual can be obtained by constructing an orthonormal basis starting from $v$, then taking the wedge product between the other elements, and dividing by the length of $v$. The result is from $\wedge^{n-1}V$, not from $V^*$. All these three spaces are isomorphic, in a canonical way, and also with $\wedge^{n-1}V^*$, by composing the two kinds of dualities. But the two dualities refer to totally distinct isomorphisms.
In connection with Electrodynamics (in Lorentzian spacetime), the Hodge dual of the electromagnetic tensor appears in Maxwell's equations:
$$d F=0$$
and
$$d *F=*J$$
where $J$ is the current $1$-form. These two equations contain the four Maxwell equations. Here, $*F$ is the Hodge dual of the electromagnetic tensor $F$, and $*J$ of the current $1$-form $J$ (which in turn is the "dual" in the other sense of the current vector).
Added
To be more close to the question. The equation
$$*F_{ij} = \frac{1}{2} \epsilon_{ij}{}^{kl} F_{kl}$$
represents the Hodge duality between $\wedge^2V$ and itself. But
$$*F^{ij} = \frac{1}{2} \epsilon^{ijkl} F_{kl}\tag{1}$$
is a duality between $\wedge^2V$ and $\wedge^2V^*$. There is also the duality in the first sense, between $\wedge^2V$ and $\wedge^2V^*$ (extending that between $V$ and $V^*$). So, there are two distinct isomorphisms between the vector spaces with inner product $\wedge^2V$ and $\wedge^2V^*$.