As far as I know we are using routing protocols to achieve Layer 3 connectivity, I am confused with the fact that BGP works over TCP which is L4. How can L4/TCP be established without prior L3 connectivity?
TCP/IP sockets establish an end-to-end connection through the network, between two specifically addressed end points. BGP uses TCP/IP to communicate between routers (any devices exchanging routing information.) The information exchanged is used by the BGP peers, to better choose the way they choose where to send, (aka, next-hop) packets that they need to transmit.
At the very edges of the Internet, things are easy; "everything is this way," towards your Internet provider. More in the middle, a router might have multiple choices. So it uses TCP/IP to move BGP traffic amongst its routing neighbors. The BGP information then tells the router which paths to prefer when there are multiple ways for a packet to get where it's going.
The end points (e.g. web browsers) and the routers are speaking TCP/IP. But the routers are using TCP/IP, (BGP communications composed of TCP/IP packets) to talk about what to do with the other TCP/IP packets they need to route.
Routing protocols do not "achieve" L3 connectivity. They populate the routing (forwarding) table of the router with information learned from other routers.
BGP is an "application" that runs over TCP/IP. In other words a BGP router uses TCP/IP to communicate with other BGP routers to exchange routing information.
In order for BGP to work, you must already have L3 connectivity between the routers.
The OSI network model and its layering is useful for understanding end-to-end communication between hosts, but it is not really intended to explain how the network control plane functions. There is a bootstrapping problem inherent in establishing full BGP connectivity, but the way that this bootstrapping takes place is well understood and does not have any circular dependencies.
In terms of BGP, the way that adjacencies are formed and information is exchanged depends on the type of session.
The simplest is eBGP. Typically eBGP runs on a TCP session between two directly connected routers. In this case each peer knows how to talk to the other because both of them have an interface on the same subnet, so there is no need to use an external routing protocol to form the adjacency.
With iBGP things are slightly complicated. In the simplest configuration all routers within an autonomous system will be configured as part of a full mesh, with iBGP sessions with all other routers in the network. Within the autonomous system an interior gateway protocol such as OSPF or ISIS in order to build up the internal routing topology. When the IGP has done it's job, all routers will have a routing table populated with routes to all the iBGP neighbours allowing the TCP session to form with no circular dependency.
Where things get a little more interesting is in situations where not all routers within the autonomous system run with a full BGP table. If the iBGP mesh is not complete you can get situations where a router in the middle of the network has a different view of the table that its direct neighbours. This will cause sub-optimal routing, and in some cases routing loops that will lead to traffic bouncing between devices until the TTL expires.
The link has static addresses and associated routing entries configured, which are used for establishing the BGP session. Using BGP, the routing table is then extended with the entries pointing to other networks.
As BGP is only used between direct peers, no routes other than that pointing to the other end are required at this point.
E.g. if we wanted to peer, we'd agree on a /30 or /31 subnet, assign one address to each end of the network, and create a network route for that subnet to this link, then we'd configure the other as BGP peer, at which point I get additional routing entries for all networks you announce to be sent via your router (which in turn is part of the local statically configured network route).
--- --- --- --- | D |------| A |--------| B |--------| C | --- --- --- ---
Suppose A and B are routers(in different or same AS) and D and C are hosts. Now A and B are connected to each other and can communicate. But how would D be know C's position so that it can communicate to C. Same is true for C when it wants to communicate to D. Now if we run BGP protocol between A and B, they exchange the layer 3 connectivity information to each other. In simple terms, A will tell B that D is connected to it. Then either B can convey this to C or if B is default gateway for C, in either way C can know D's position.
So in this case layer 3 connectivity information is passed between A and B, given A and B run BGP protocol.
So prior BGP connection is needed between two systems in order to exchange layer 3 routing information. I have just shown a simple example to answer your query. In practical scenario, many more amount of routing data is exchanged between BGP peers.
BGP runs over TCP protocol. So a TCP socket must be opened between them, only then they can exchange routing data.
without prior L3 connectivity?
"L3 connectivity" is not an all or nothing thing.
The administrator setting up the router will configure the interfaces with IP addresses and subnet masks. Based on these configurations implicit routing table entries will be created that allow the router to talk to it's neighbours.
Routing protocols can then run on top of this local L3 connectivity to establish longer distance L3 connectivity.