How to deal with functions of kinematic quantities not defined in terms of time?

You use what is called the chain rule in calculus, which basically states that if $x$ is a function of $y$ and $y$ is a function of $z$ then

$\displaystyle \frac {dx}{dz} = \frac{dx}{dy} \frac{dy}{dz}$

In the example you gave, $v(x) = kx^2$ we have:

$\displaystyle a = \frac {dv}{dt} = \frac {dv}{dx} \frac {dx}{dt} = (2kx)v$

From this and the relation $kx = \sqrt{kv}$ we may express $a$ as a function of $v$:

$a(v) = (2\sqrt{kv}) v = 2 k^{1/2}v^{3/2}$

Also:

$a(x) = (2kx)(kx^2) = 2k^2x^3 \\ \displaystyle \Rightarrow x(a) = \left( \frac {a} {2k^2} \right) ^{1/3} \\ \displaystyle \Rightarrow x(a^2) = \left( \frac {\sqrt{a^2}} {2k^2} \right) ^{1/3}$

We can't, from the information given, find $v(t)$. To find this we would have to be given $x$ as a function of $t$ or $a$ as a function of $t$.

Let us say you have some $v(x)$, i.e. velocity in terms of position $x$. From elementary physics, we know that:

\begin{align}v = \frac{dx}{dt}\end{align}

So now since we know velocity $v(x)$ in terms of $x$, all we are left with is to solve the above differential equation and find the position in terms of $x$.

Once we have obtained the position in terms of $x$, we would be able to obtain the rest of the required physical quantities by simple substitution, differentiation and inversion of functions.

This is also true if acceleration is given in terms of position as well. The principle mathematics is solving differential equations. In case of velocity, it was a first order differential equation and in case of acceleration a second order differential equation.

A famous example of this would be solving the simple harmonic motion.

P.S: I hope you know what differential equations are.

first solve this differential equation

$$\frac{dx}{dt}=v=k\,x(t)^2$$

with $~x(0)=x_0~$ you obtain

$$x(t)=-{\frac {x_{{0}}}{k\,t\,x_{{0}}-1}}\tag 1$$

$$v(t)=\frac{dx}{dt}={\frac {k{x_{{0}}}^{2}}{ \left( k\,t\,x_{{0}}-1 \right) ^{2}}}\tag 2$$

and $$~a(t)=\frac{dv}{dt}=-2\,{\frac {{k}^{2}{x_{{0}}}^{3}}{ \left( k\,t\,x_{{0}}-1 \right) ^{3}}}\tag 3$$

to obtain a(v) , obtain t(v) from equation (2) :

$$t(v)=\pm {\frac {v+x_{{0}}\sqrt {k\,v}}{v\,k\,x_{{0}}}}\\ a(v)=a(t(v))=-2\,{k}^{2}{x_{{0}}}^{3} \left( {\frac {v+x_{{0}}\sqrt {kv}}{v}}-1 \right) ^{-3} $$

and $$~a(x)=a(v=k\,x^2)=-2\,{k}^{2}{x_{{0}}}^{3} \left( {\frac {-x_{{0}}+x}{x}}-1 \right) ^{-3 } $$

you can use this equation to get $~x=x(a)~$ and $~x=x(a^2)~$