It appears there is a single option (the first) which will not require working together with the DM. Otherwise, I have heard that some DMs are partial to pizzas, beers, or car-washing.
Extra Domain
Certain classes, such Seeker of the Misty Isles (Complete Divine, p. 61) gain the Travel Domain as an extra Domain even if the deity of the character does not offer it1.
There is no restriction in the rules for converting a Domain:
In addition, you can choose to give up access to a Domain in exchange for the corresponding domain feat. Doing so allows you to select up to three Domain feats, but you cannot prepare Domain spells or use the granted power of the sacrificed Domain. In essence, you trade in a Domain for an extra
feat slot that you can spend only on a specific Domain feat.
Of course, becoming a Seeker of the Misty Isles comes with its own restrictions, notably being an Elf, which may not fit a particular character.
1 This is unlike a Contemplative who gains an extra Domain from the ones offered by their deity.
Conversion
A character not following a specific deity can select Travel Devotion as a first Domain feat with little restrictions as per Domain Feats (Complete Champion, p. 52):
For characters who do not worship a particular deity, use the following guidelines for which Domain feats allow or preclude the selection of others. This should be done in concert with the DM.
and
If you do not follow any specific deity, your basic system of beliefs should support your Domain feat choices. A good rule of thumb is to designate one to three Domains (in addition to that corresponding to your first Domain feat) that are important to you. These beliefs must also be consistent with your alignment.
Furthermore, the case of converting into a follower of a particular deity is not covered. There is no mention of losing, or having to convert, any pre-existent Domain feat when becoming a follower of a deity who does not offer the specific Domain.
This is a case of your DM stepping in. Still, following the above, a character could first pick Travel Devotion, for example starting with a few levels of Crusader, and only afterwards become a Cleric of Wee Jas.
No Domain.
Only characters with levels in classes with access to Domains, such as Cleric, are strictly limited to the Domains offered by their deity.
A Domain feat usually corresponds to one of the domains to which a particular deity grants access, or those representing a set of ideals.
Avoiding character classes who gain access to a Domain therefore makes it possible to avoid the restriction above, although picking Travel Devotion will limit the selection of any other Domain feat as per Domain Feats (Complete Champion, p. 52):
You can select a Domain feat at any level. Once you have chosen one, however, you cannot select another unless the second fits thematically with the first.
and
Usually, domain feats go together only if they correspond to the domains offered by the deity you follow.
Obtaining Turn or Rebuke Undead to satisfy the Ruby Knight Vindicator and Divine spellcasting to benefit from its spellcasting progression without gaining access to domains is left as an exercise to the reader.
Be an heretic.
The Heretic of the Faith feat (Power of Faerûn, p. 46) allows, among other things, exchanging any one Domain you have access to for one you do not normally have access to.
The first issue is that this a Forgotten Realms feat, while Wee Jas is a Greyhawk deity, so there is a conflict of settings.
Furthermore, taking the feat implies being judged as one of the False (Forgotten Realms Campaign Setting, p. 250) in most cases:
Moreover upon your death you are judged one of the False unless your deity specifically intervenes on your behalf with Kelemvor. Without the use of the Miracle or Wish spell, this does not happen unless your heresies are adopted by the deity and the faith as a whole. It is theoretically possible that such intervention could occur long after your death, but such cases are vanishingly rare.
And being judged as one of the False, apart from the eternal torment one soul's endures after death, also has the mechanical consequence described in The City of Judgment (Forgotten Realms Campaign Setting, p. 250):
There is no respite for the False unless Kelemvor wills it, and in this tenure he has not been known to change his mind. Furthermore once Kelemvor has made his judgement, the sould cannot be raised or resurrected without the intervention of a deity (represented by at least the use of a Miracle or Wish spell), who will almost certainly have to negotiate with Kelemvor.
Where the conflict of setting is evident, since both Wee Jas (in Greyhawk) and Kelemvor (in the Forgotten Realms) are described as having dominions over funeral rites and the faithless dead. Though given Wee Jas fiery temper, maybe being judged by Kelemvor is preferable to being brought in front of her as an heretic.
Adapt the Ruby Knight Vindicator
Toward the end of the Ruby Knight Vindicator entry is an Adaptation section (Tome of Battle, p. 125):
Although this prestige class is specific to a single crusader order — the Ruby Knights of Wee Jas — you could easily adapt it to crusaders devoted to almost any other deity. For example, the faiths of Hextor, Vecna, or St. Cuthbert could
easily support secret vindicator organizations.
For example, keeping in with the death theme, Kelemvor offers both the Law and Travel domains. Also, Kelemvor's favored weapon is a Bastard Sword, instead of a Dagger.
At this point, though, it may well be that Travel Devotion is simply not worth the expenditure; especially when considering that Initiators have many Strikes working off a Standard Action, thereby allowing moving and initiating a Strike.