In MRI the term $k$-space usually means that you have spatial frequencies in a matrix. The Fourier Transformation of this matrix is the image.
The terms readout and frequency correspond to each other; they mean the same. The readout direction is a logical direction, along which a gradient is applied during signal acquisition, i.e. during readout. This gradient field causes a frequency spread of the excited magnetization along the direction of this gradient, hence the second name readout for this direction and for the corresponding signal axis in $k$-space.
The term phase is associated with another direction, usually perpendicular to the readout/frequency direction. It is called so, because a gradient field is applied before the signal is read out. This causes a frequency shift, too, but the gradient field is switched off before the read out of the signal, hence in this direction there is only one frequency during read out. What is left from this frequency spread is a phase shift of the magnetization vectors along that direction. The trick here is to repeat the measurement with different field strengths of that phase encoding gradient - that way, this direction is fully encoded.
Of course you are right: The coil that measures the signal does measure it in a time-domain. Keep in mind, that you additionally switch magnetic gradient fields. These fields act upon the magnetization and hence alter the measured signal. Since the temporal behavior of those gradient fields is known and chosen carefully (to fulfill certain criteria such as the Sampling Theorem, etc.), there is a simple relation between the time $t$ of the measured signal and the corresponding $k$-space position: $\vec{k}(t) = \frac{\gamma}{2\pi}\int_0^t \vec{G}(\tau)\,\textrm{d}\tau$.
Note: Even though the phase and readout gradients look completely different in sequence diagrams and appear to be completely different encoding techniques - they are completely the same! Even for physicists who are new to the field of MRI this bears some trouble initially in understanding the image measurement process.
