Given a $n+1$ dimensional manifold $M$ one by definition has charts or coordinates that are homeomorphic to $\mathbb{R}^{n+1}$. This is independent of any Lorentzian or Riemaniann metric on $\cal{M}$.
Now if the manifold $M$ admits a Lorentzian metric $g$ then the coordinates use to define the manifold also define the components of the metric.
A common way to define a spacetime even if it is not know the whole manifold $M$ is to work locally. Even if the topology of $M$ is not $\mathbb{R}^{4}$, locally it is. Then using the local (flat) coordinates one define locally a metric and imposing some symmetries and physical conditions one can arrive to relevant metrics such as the Schwarzschild metric.
However, another way to find solutions to Einstein's equations is to see them as an initial value problem. That is given on a hypersurface $\Sigma$ the first and second fundamental form one can determine a Lorentzian manifold $M$ using Einstein's equations.
Regarding your comment of how to make the sense of coordinates. In this case we have chosen an initial n-dimensional $\Sigma$ where we know the coordinates by definition. Then, also one define a lapse function $N$ and shift vector $\beta$ on $\Sigma$. These choices define locally a chart with topology $M={\mathbb{R}} \times {\Sigma}$. The choice of the lapse and shift sometimes are related with physical observers, but others are used for mathematical convenience such as the harmonic slicing. See section 9 This define the $n+1$- dimensional coordinates on $M$. In fact this is the topology of all globally hyperbolic spacetimes.
However, this is only a local characterization. If one wants the total manifold then one is interested in maximal extensions. For example, the chart you used has a well know coordinate singularity at $r=2M$ and therefore one needs to change the chart and coordinates to cover the full spacetime. Notice that the existence of the singularity is responsible for the change in the global topology.
The concept of maximal extension is related to geodesic completeness or the well-posedness of Einstein equations (no curvature singularities). If this two criteria are equivalent is part of the Strong Cosmic Censorship.
The global case which correspond to the question of the maximal extension of the space-time as as a well-posed problem of Einstein's equations is an active area of research. The Strong Cosmic Censorship deals with the uniqueness of global solutions.
A frame (at an event $E$) is an ordered basis for the tangent space to spacetime at $E$. A coordinate system is a diffeomorphism from an open subset of spacetime to an open subset of ${\mathbb R}^{3+1}$.
(More commonly, such a diffeomorphism is called a "chart" and its inverse is called a coordinate system, but I'll use the slightly less common language.)
A frame at $E$ induces a coordinate system on the tangent space at $E$ (call it $T_E$) in the obvious way --- given a frame $(v_1,v_2,v_3,v_4)$, map the point $\Sigma a_iv_i$ to $(a_1,a_2,a_3,a_4)$.
Let $U_E$ be the image of the exponental map from $T_E$. Then composing with the inverse of the exponential map gives a coordinate system on $U_E$.
So every frame yields a coordinate system.
Conversely, given a coordinate system $(\phi_1,\ldots,\phi_4)$ on any open set containing $E$, we get a frame $(\partial/\partial\phi_1,\ldots,\partial/\partial\phi_4)$ at $E$. So every coordinate system yields a frame.
The composition
$$\hbox{Frames}\rightarrow\hbox{Coordinate Systems}\rightarrow\hbox{Frames}$$
is clearly the identity. The composition in the other direction is clearly not the identity (think of a polar coordinate system, for example).
The coordinate systems that come from frames are called normal, so there is a one-one correspondence between frames and normal coordinate systems. Sometimes in informal language, a frame and the corresponding coordinate system are identified.
(There's also a version of this where the frames are required to be orthonormal, which is sometimes tacitly assumed.)
Best Answer
General relativity only has local frames of reference, not global ones. In general relativity, coordinate systems are entirely arbitrary, and we can't typically take a coordinate system and relate it in any meaningful way to a the frame of reference of some observer.
In Newtonian gravity, there is an implicit assumption that an observer can and does know about the current state of all matter in the universe. Without this information, there would be no way to apply Newton's laws, since gravity is a long-range force acting instantaneously at a distance, and there would also be no way to determine what was an inertial frame of reference. Traditionally, the frame of the "fixed stars" was considered to be a good enough inertial frame of reference for all practical purposes, and it was implicitly assumed that we could observe the stars instantaneously, neglecting any possible delay due to the time taken for light to propagate. Other frames of reference in uniform motion relative to this frame were also valid. Each these frames of reference was described by a certain coordinate system, and the different coordinate systems were connected by rotations and Galilean boosts.
In special relativity, it gets harder. We can't instantaneously observe all of space, but we don't need to, because in order to make predictions about our own neighborhood, we only need to know the conditions inside our own past light-cone, i.e., at events that are close enough in space and far enough back in time so that signals have had time to get from them to us. For convenience, we still usually go ahead and extend this description to include all of spacetime, which implies a sort of elaborate surveying system whose results are known to us only much later. For example, the surveyors might have to place clocks in various positions and synchronize the clocks by exchanging radio signals. Time is relative, but for an observer in a certain state of motion, we can define a notion of simultaneity. Each inertial observer corresponds to a set of Minkowski coordinates, which are the result of the surveying process.
In general relativity, basically all of this goes out the window. Coordinate systems may not be able to cover all of spacetime, for the same reason that we can't put a coordinate system on the earth's surface without having it misbehave in certain places such as the poles. Even for spacetimes, such as FLRW cosmological spacetimes, for which it is possible to have such a global coordinate system, these coordinates cannot be identified with observers or frames of reference. Frames of reference exist only locally, i.e., at scales small compared to the scale set by the curvature of spacetime. When we discuss what an observer "sees" in general relativity, we mean exactly that: the optical signals that they receive.
Example: An observer outside a black hole will never see infalling rock pass through the event horizon. This is trivially true, because the event horizon is defined as the boundary of the region that is externally unobservable. This does not mean that the observer's frame of reference corresponds to some set of coordinates, or that what the observer sees can be explained by such coordinates. What the observer sees is simply explained in terms of the trajectories of the light rays that travel from the rock to the observer's eye.
Example: General relativity doesn't tell us whether distant galaxies are "really" moving away from us, or whether they're "really" at rest while the space in between fills up. We only have a local coordinate system, not a global one that would allow us to define and measure velocity vectors for distant objects. We can define things like coordinate velocities, but they're not particularly meaningul, because coordinates are arbitrary.
Example: Given a flat spacetime with Minkowski coordinates $(t,x)$, we can define new coordinates $(t,u)$, where $u=ax+(1/4)\sin ax$ and $a$ is a constant. There is nothing wrong with these coordinates, because the transformation is one-to-one and smooth, but these coordinates clearly don't correspond to the frame of reference of some observer.
People often get confused about this kind of thing because of historical treatments of general relativity, including Einstein's own popularizations. Einstein's original inspiration for general relativity had to do with a set of concepts including Mach's principle and the notion of extending the set of allowable frames of reference to include accelerated ones. General relativity is now over a century old, and many of Einstein's original vague inspirations have not turned out to be the best way to think about these things.