my car for whatever reason stays up around 13.5V
It's supposed to: the nominal
"12V" battery is actually supposed to charge up to about 12.6V (some details on wikipedia
). Car alternators run about 13.5-14V because you need a voltage higher than the battery's to charge it. Older alternators, without the benefit of solid-state charging controls, will peak even higher as the RPMs go up.
Relays are designed to tolerate a range of voltages around their nominal rating. Unless you're planning to have it on for hours at a time, I wouldn't worry about even a relay not
designed for "automotive" use suffering from the higher voltage.
Since you're in TX, I'd suggest shopping at either BG Micro
for surplus "automotive" relays: you'll probably save enough from retail just on the relays to pay for the shipping. Plus you'll find other goodies you'll want for future projects.