There is actually still a slight field for improvement
- RAW, you should be able to buy horses, and they should be skeletal horses. They can tirelessly hustle at 10 mph. Creating them would cost you anywhere between 525 and 900 gp, and this is the fastest option you can have at these levels.
- If you cannot use horses, combine the things you listed in your answer with having a forced march for an hour or two and removing fatigue with a wand of Lesser Restoration.
You have listed pretty much every affordable way of increasing your land speed. However, it is still possible to improve your travel a little bit, assuming that:
- Your DM actually follows the rules and doesn't introduce house rules
- You have no more than 900 gold for your party of 4-5 characters to spend on the adventure.
This indeed multiplies your overland travel speed by 10%, but if your movement is impaired, it gives you a 25% increase instead. Your speed will be 110% on a jungle "highway", but 93.75% on a jungle road or trail (the usual speed there is 75%).
We have spent 15 gp per person so far.
Hiring a Skald
There are no rules given for hiring an NPC with levels in a PC class. The cost is to be determined by the GM. The best you can find is this level 1 Foot Soldier who can join a party for a share of loot. I have never played in such a party, but you can just introduce such a character as a full NPC with class levels that will join your party via role play, earn XP and money, and generally act as and be a fully-fledged character.
Your other option is the Leadership feat, which would allow you to have a level 3 Skald once you hit level 3 yourself. If you don't aim to abuse this feat and are quick with your decisions, it's not going to break your game.
This allows you to march for 8 hours per day and pretty much max your overland speed and effectively move at 220% speed over jungle highway and 187.5% through jungle road or trail.
Healing away that damn non-lethal damage from hustling&forced marching
Actually, you don't need a Skald, because all that happens when you march too quickly is:
- You get non-lethal damage.
- This damage makes you fatigued.
If you heal the damage, the fatigue goes away:
"Eliminating the nonlethal damage also eliminates the fatigue."
Note that the rule says "eliminate", not heal, so not every GM would agree with this way of reading the rule book.
A healing wand could heal this damage away very cheaply, for 15 GP per use.
Casting Lesser Restoration to remove the fatigue
Even if your GM doesn't agree that healing removes the fatigue, a wand of Lesser Restoration costs 750 gp if created by a Paladin, or the same 15 gp per use. You can march, become fatigued, heal non-lethal damage, and cast Lesser Restoration upon yourself.
Combine a Skald's bonus with trekking poles, forced march, and Lesser Restoration
A properly-built Skald could give you (practically) unlimited hustling per day, essentially doubling your speed, which is 3 mph usually or 6 mph when marching. If we assume failing every Constitution check to start a forced march, here is what you can do:
- Hustle for 8 hours.
- Hustle for an additional your.
- If you fail your Constitution check, heal those 1d6 points of non-lethal damage (15 gp) and take one use of Lesser Restoration (15 gp).
- Go to 2.
Each additional hour of marching costs you 30 gp per person. Of course, you are not actually going to fail every single Constitution check, so you can just march until one of you fails a check, restore yourselves, and go to bed. Assuming that everyone has CON 14 (and you probably shouldn't have less), each of you has a 35% chance of failing the first Con check, and a party of 5 characters will expand 1.75 points of their "restoration kit", paying 52.5 gp for a party's average first hour of a forced march. This allows for 17-18 days of marching given the budget listed at the beginning, minus 125 gp for the trekking poles, which gives us a total of about 15 days in this traveling mode.
If your party has better Consitution scores, you will be able to take a little bit more risks for the same price.
Now, I do understand that you can't buy half a wand with 25 charges, and a full wand costs 750 gp, but you should be carrying a healing wand anyway, while a wand of Lesser Restoration is still not a must at this level, so I assume you to be able to have both.
Doing the math
You march for a total of 9 hours. The Skald allows you to hustle for this whole time. You get a speed of 54 miles per day on a highway. A trekking pole adds another 5.4 miles, giving you a speed of 59.4 miles per day. That's actually quite impressive, given that a normal party without marching coffee only traverses 27 miles per day.
If moving through a trail, your speed is 54*3/4=40.5 miles per day, multiplied to 50.63 miles by your trekking pole.
For a completely Trackless Jungle, just divide this speed by 3 for 16.77 miles per day.
But... what about animals?
Aurochs have a Con score of 17 (+3) and Endurance as a feat, which gives another +4 to a roll to avoid the fatigue, for a total of +7. Their individual chance to fail the first Con check is 10%, giving you an average cost of 3 gp per hour of marching. You probably do need to take this into account if you have more than one.
And what if my GM does not ban horses as mounts in the jungle?
Horses will automatically fail any checks to avoid fatigue, so it should either be Skeleton Mounts, who ignore the checks, or summoned horses, who are disposable.
Summoned horses cost 15 gp per 2 hours of marching per person if you use wands, and it's probably a bit too much. If you have a level 4 Summoner in your party, they can expand their spell slots to summon Phantom Steeds and Mounts, but it is going to pretty much exhaust their magic reserves every day.
I have not found a price for a skeleton horse, but it has 2 HD, costing 50 gp in onyx to Animate it. At level 4, you also can't cast this spell yourself. You need to seek service of a level 10 Cleric, who will cast it for you for 10*3*10=300 gp, where 10 is his Caster Level, 3 is the Spell Level, and 10 gp is a fixed multiplier. A light horse costs 75 gp, plus 50 gp in onyx, for a total of 600 gp per party of 5 adventurers. Of course, you might argue that a light horse's body is worth a lot less than a healthy, alive horse, but I am giving you a maximum price. This exhausts your travel budget immediately, but it's actually the fastest mode of movement you can have.
A skeletal horse moves at 5 miles per hour and can hustle without any problems, and force march, too. Just move at 10 mph as much as you guys can. Don't take any oxen, the undead mounts will carry stuff on themselves.