Yeah, you could just have a lookup table that's ASCII characters to "long phrases," and encode the URL that way. Have a bunch of nonsense phrases per character and select them randomly, but as long as the lengthened URL fully encodes the destination URL, there's really no scaling problems to be had. You could even do the whole thing in client-side Javascript if you went that route, purely static site.
You still need a service to redirect the urls.