In coordinate-free relativity, how do we define a vector? Relativity can be developed without coordinates: Laurent 1994 (SR), Winitzski 2007 (GR).
I would normally define a vector by its transformation properties: it's something whose components change according to a Lorentz transformation when we do a boost from one frame of reference to another. But in a coordinate-free approach, we don't talk about components, and vectors are thought of as immutable. For example, Laurent describes an observer using a timelike unit vector $U$, and then for any other vector $v$, he defines $t$ and $r$ uniquely by $v=tU+r$, where $r$ is orthogonal to $U$. The $(t,r)$ pair is what we would normally think of as the coordinate representation of $v$.
In these approaches, how do you define a vector, and how do you differentiate it from things like scalars, pseudovectors, rank-2 tensors, or random objects taken from something that has the structure of a vector space but that in coordinate-dependent descriptions would clearly not transform according to the Lorentz transformation? It seems vacuous to say that a vector is something that lives in the tangent space, since what we mean by that is that it lives in a vector space isomorphic to the tangent space, and any vector space of the same dimension is isomorphic to it.
[EDIT] I'm not asking for a definition of a tangent vector. I'm asking what criterion you can use to decide whether a certain object can be described as a tangent vector. For example, how do we know in this coordinate-free context that the four-momentum can be described as a vector, but the magnetic field can't? My normal answer would have been that the magnetic field doesn't transform like a vector, it transforms like a piece of a tensor. But if we can't appeal to that definition, how do we know that the magnetic field doesn't live in the tangent vector space?
Bertel Laurent, Introduction to spacetime: a first course on relativity
Sergei Winitzki, Topics in general relativity, https://sites.google.com/site/winitzki/index/topics-in-general-relativity
 A: Honestly, this coordinate-free GR stuff (Winitzki's pdf in particular) looks like GR as would be taught by a mathematician--very similar to do Carmo's text on Riemannian geometry. In classic (pseudo-)Riemannian geometry, vectors are defined as derivatives of affine parameterized curves, covectors as either maps on vectors to scalars or as gradients of scalar fields.  Something like the Riemann tensor is defined as a map on two/three/four vectors spitting out two vectors/one vector/a scalar.
Differential geometers love defining everything as a mapping; I consider it almost a fetish, honestly.  But it is handy: defining higher-ranked tensors as mappings of vectors means that the tensor inherits the transformation laws of each argument, and as such, once you establish the transformation law for a vector, higher-ranked tensors' transformation laws automatically follow.

Edit: I see the question is more how one can figure out a given physical quantity is a vector or higher-ranked tensor.  I think the answer there is to look at the quantity's behavior under a change of coordinate chart.
But Muphrid, we never chose a coordinate chart in the first place; isn't that how coordinate-free GR works?
Yes, but the point of coordinate-free GR is just to delay the choice of the chart as long as possible.  There is still a chart, and most results depend on there being a chart, just not on what exactly that chart is.
How does looking at a change of chart (when we never chose a chart in the first place) help us?
The transition map from one chart to another is a diffeomorphism, and so its differential can be used to push vectors forward or pull covectors back.  Hence, the transformation laws that usually characterize vectors and covectors are still there.  They look like this:  let $p \in M$ be a point in our general relativistic manifold.  Let $\phi_1: M \to \mathbb R^4$ be a chart, and let $\phi_2 : M \to \mathbb R^4$ be another chart.  Then there is a transition map $f : \mathbb R^4 \to \mathbb R^4$ such that $f = \phi_2 \circ \phi_1^{-1}$ that changes between the coordinate charts.
Thus, if there is a vector $v \in T_p M$, there is a corresponding vector $v_1 = d\phi_1(v)_p \in \mathbb R^4$ that is the mapping of the original vector into the $\phi_1$ coordinate chart.  We can then move $v_1 \to v_2$ by the (edit: differential of the) transition map.
But Muphrid, aren't we meant to be working with the actual vector $v$ in the tangent space of $M$ at $p$, not its expression in a chart, $d\phi_1(v)$?
You might think so, but (as was drilled to me repeatedly in a differential geometry course) we don't actually know how to do any calculus in anything other than $\mathbb R^n$.  So I think there's some sleight of hand going on where "really" what we do all the time is use some chart to move into $\mathbb R^4$ and do the calculus that we need to do.
What this means is that, in my opinion, coordinate-free is a bit of a misnomer.  There are still coordinate charts all over the place.  We just leave them undetermined as long as possible.  All the transformation laws that characterize vectors and covectors and other ranks of tensors are still there and still let you determine whether an object is one or the other, because you're always in some chart, and you can always switch between charts.
A: There are 4 common definitions of tangent vectors, some of which make use of coordinates only casually or even not at all.
Definition via transformation laws
There's a somewhat technical one preferred by some physicists (those who value calculation rules over geometric insight - shut up and calculate, you probably know the type): A vector is just an $\mathbb R$-tuple that obeys certain transformation laws under a change of coordinates.
This definition actually makes sense in context of the Erlangen program, as the tangent space is a vector bundle associated to the principal bundle of linear frames. However, as tangent spaces are normally introduced long before lie groups and principal bundles, the definition appears unintuitive.
Definition as equivalence classes of curves
A more intuitive one defines a vector as an equivalence class of curves tangent to each other. We need to make use of coordinates to define the necesary first-order contact of curves, but this use is far less prominent.
This definition makes clear why tangent vectors should be considered velocities and comes with a natural generalization to higher jet spaces.
Definition as derivations
We arrive at a totally coordinate independent characterization by identifying vectors with their directional derivatives: A vector is just a derivation, ie a linear functional that respects the Leibniz rule.
That's the definition that can be found in (most?) modern literature on differential geometry (where modern means something like the 60s).
Algebraic definition
Another coordinate-free (but very abstract one) comes from algebraic geometry, and Muphrid braught it to my attention just yesterday: There's a purely algebraic definition of the cotangent space, and the tangent space is just its dual.
I suspect the algebraic definition can probably be made more concrete (from an analytic point of view) in terms of infinitesimals (see Advanced Calculus by Sternberg for a definition of infinitesimals that makes sense in standard analysis, but is of course not identical to the non-standard one).
A: From MTW's "Gravitation" (via Google Books):


Updated answer to edited question:

For example, how do we know in this coordinate-free context that the
  four-momentum can be described as a vector, but the magnetic field
  can't?

I'm reminded of a relevant section from "A First Course in General Relativity" by Schutz.  In section 4.4 on the stress-energy tensor:

In the frame $\bar O$ we again have the number density is $\gamma n$,
  but now the energy of each particle is $\gamma m$ since it is moving. 
  Therefore the energy density is $\gamma^2 mn$:
$ \gamma^2 \rho = $ energy density in a frame in which particles have
  velocity v
This transformation involves two factors of $\gamma$ because both
  volume and energy transform.  It is impossible, therefore, to
  represent energy density as some component of a vector.  It is, in
  fact, a component of a [2nd rank] tensor.

A: 
I'm not asking for a definition of a tangent vector. I'm asking what criterion you can use to decide whether a certain object can be described as a tangent vector. For example, how do we know in this coordinate-free context that the four-momentum can be described as a vector, but the magnetic field can't?

If I understand your clarification correctly, your question is actually about modelling of physical systems, and my answer is generic:
Same as with any other physical theory, by comparing the predictions of our model with experiment.
Regardless if we use coordinates or coordinate-free language, the geometry predicts properties (eg transformation laws) and allowed operations (eg contraction) by modelling physical quantities as geometric ones.
Take elektrodynamics: In the non-relativistic setting, we deal with electric and magnetic 3-vectorfields and use the cross product to define the Lorentz force. We do it this way because experiment tells us that's how reality works at some level.
Now, if we try to make a relativistic theory from that, we cannot make use of 3-vectors or cross products, and it turns out that the right way to model the electromagnetic field is as a 2-form, the Lorentz force law ending up as contraction with the velocity 4-vector.
The benefit of the relativistic formulation is that we get the correct transformation laws for free, ie they are an inherent part of our model.
Now, a 2-form is a very generic object, and we could ask ourselves if there's a way to understand where it comes from or if there's additional geometric structure. This leads us to classical gauge theory on principal bundles.
Another case in point would be the general setting of relativistic mechanics: Relativistic systems should be reparametrization-invariant, and we can formulated such world-line dynamics by going from ordinary jets to jets of submanifolds.
What's the benefit of using coordinate-free language over coordinates in this? Personally, I see it as a form of sanity check: Not being able to write down an equation that turns up in your model in coordinate-free language is a design smell and tells you that you've missed part of the relevant structure.
Take the equations of motion of classical mechanics:
From a birds-eye view, dynamics are given by a vector field $Z$ on some manifold.
In Newtonian and Hamiltonian mechanics, it can be defined in coordinate-free language via
$$
(\pi\circ F)_*Z = F
$$
where $\pi:\mathrm{TT}^*M\to\mathrm{T}^*M$ and
$$
Z\rfloor\omega = \mathrm dH
$$
respectively.
I don't know how to do this in case of the Euler-Lagrange equations, and in fact I have to admit that I haven't really internalized the geometric structure of Lagrangian theories (see eg arXiv:0908.1886 and this PDF).
For now, I'm content to just go to a Newtonian description
$$
(\mathbb FL)_*Z = \iota\circ\mathrm dL
$$
via the natural isomorphism $\iota:\mathrm{T}^*\mathrm{T}M\to\mathrm{TT}^*M$, or even to a Hamiltonian formulation
$$
Z\rfloor\mathbb FL^*\omega = \mathrm dE
$$
A: I include a few comments here, my apologies if they fail to be relevant.
I happen to be reading Cartan for Beginners by Thomas Ivey and J.M Landsberg. In the first Chapter they describe how to "do" differential equations without coordinates. It's very beautiful. At some point the mathematics of Exterior Differential Systems is worth a look because they are very much interested in finding a systematic method of converting coordinate-based theories into geometrized models on jet-space. 
From a physics perspective, given the importance of the Lagrangian formulation of things. The question comes down to how to construct an invariant Lagrangian (or perhaps almost invariant  up to some term which vanishes on the boundary...). Well, how do we construct such things?
We have to extract a scalar somehow.
For group-valued objects we need some trace to remove the matrix and obtain a number.
For each contravariant index we need a covariant index with which to contract. In my view, the coordinate free version of a vector is simply a mathematical object which packages the needed transformation law. It's entirely equivalent to work with equivalence classes of vectors where equivalence is judged by the transformation law. From a math perspective, it's much simpler to think in terms of bases and coordinates. But, when I think about building a Lagrangian I have to admit the component index approach has a certain computational beauty. Moreover, some of the coordinated objects have a lot of exterior algebra hidden. For example, if I understand correctly, the formulas for the derivative of the dual to the Faraday tensor in Griffiths are actually the coordinate formulas for the coderivative of the dual of the Faraday. 
Of course, we also have spinor indices. We can contract against different types and obtain new scalars in this manner.
I think the real question is how to construct invariants.
A: Mathematicians have their axioms to define what a vector is, physicists start with a vector as a physical quantity that has a magnitude and a direction. Or at least, this is how Feynman defines it in volume 1, 11-4 of his lectures on physics. These two properties belong to the object and can't possibly depend upon the coordinates used to label them.
Edit:
From Ben's comment, I'd like to add that we choose some arbitrary vector as a standard, and use that to measure the magnitude and direction of the rest of the vectors. This process can't possibly depend upon the coordinate system we use to label the components of a vector.
