I dunno, maybe if he was a Mammoth Rider.
They get Huge mounts.
Playing a large character is already in the realm of GM fiat (as core contains no large races) and is already going to end up with multiple exceptions to the assumptions the rules were written on, so talk to your GM. A mammoth or other huge herbivore makes sense to me as a mount.
I built a large cavlier, and it turns out there are no creatures he can ride.
Is there ANY mount he can ride.
First: it says "The GM might approve other animals as suitable mounts."
As you are large he should.Also, be a Beast rider, by 7th level you get Large/huge mounts.
http://www.d20pfsrd.com/classes/base-classes/cavalier/archetypes/paizo---ca valier-archetypes/beast-rider
Just apply the template they mention twice to get huge.
Why even get into a template? Take a horse and increase the size one step.