I wrote something that makes this process algorithmic (and tries to simplifying the resulting algebra as much as possible) in Magma.
Copy and paste the following code into Magma (e.g. the calculator at http://magma.maths.usyd.edu.au/calc/)
_ := PolynomialRing(Rationals());
F := NumberField(x^2-2); // s = sqrt(2)
_ := PolynomialRing(F);
K := ext<F | xF^2 - s>; // w = 2^(1/4) = sqrt(s)
ZK := Integers(K);
// find small primes that are not split in K
pps := [pp : pp in PrimesUpTo(20,F) | #Factorization(ZK!!pp) eq 1];
// Compute a quaternion algebra (over F) ramified at 2 finite primes and no infinite places
B := QuaternionAlgebra(&*pps[1..2]);
B;
// Verify ramification
RamifiedPlaces(B);
RamifiedPlaces(ChangeRing(B, AbsoluteField(K)));
_<x> := PolynomialRing(Rationals());
F<s> := NumberField(x^2-2); // s = sqrt(2)
_<xF> := PolynomialRing(F);
K<w> := ext<F | xF^2 - s>; // w = 2^(1/4) = sqrt(s)
ZK := Integers(K);
// find small primes that are not split in K
pps := [pp : pp in PrimesUpTo(20,F) | #Factorization(ZK!!pp) eq 1];
// Compute a quaternion algebra (over F) ramified at 2 finite primes
// and no infinite places
B := QuaternionAlgebra(&*pps[1..2]);
B;
// Verify ramification
RamifiedPlaces(B);
RamifiedPlaces(ChangeRing(B, AbsoluteField(K)));
The algorithm it uses is probabilistic, since there is no clear "best" quaternion algebra with specified ramification set (and anyway may be expensive to compute). Anyway, on this run it tells me
Quaternion Algebra with base ring F, defined by i^2 = -s - 1, j^2 = 8*s + 11
Quaternion Algebra with base ring F, defined by i^2 = -s - 1, j^2 = 8*s + 11
So you can take $i^2 = a = -\sqrt{2}-1$ and $j^2 = b = 8\sqrt{2}+11$; these are elements of smaller norm than you could get from $\mathbb{Q}$.