I decided to provide some information on which way I finally went for my tiled map service. Pure JavaScript and GeoJSONs weren't a solution, because I have to handle roughly 40k polygons and 33k points. So I went for tiling. Oh, and I still don't have a access to root server, so I can't set up GeoServer or something similar (wouldn't be financially feasible for a single client at the moment)
After some researching and reading, I finally settled with OpenLayers (after some showcasing with GMaps). Eric Hazzard's great book "OpenLayers 2.10" (Packt Publishing, 2011) really, really helped me a lot because it also covers some JavaScript basics and debugging tips.
I did all my vector data work in QGIS, of course, thats definitely the way to go for a small freelancer like me (I also know quite some ArcGIS stuff from university, but QGIS has been offering all I ever needed so far).
Styling the map and creating the tiles was a bigger challenge. First, I went along with "GMapCreator" by CASA, but layering multiple shapefiles proved to be tedious (I have to provide point data over polygons, and then a municipal borderline enclosing everything). It is absolutely possible to do this in GMapsCreator (and I did it for the showcase stage), but it takes 3 full rendering cycles (first you create tiles, then the existing tiles get "overdrawn" with later features - rendering in the right order is important!), and the styling menus are slightly bulky and confusing. Saving your map and editing it later is also a complicated issue.
TileMill seemed very promising, especially their CSS-like styling, so I looked into it. Unfortunately, it's Mac or Linux only, so that might scare some people off. I really liked what I saw, so I set up a Ubuntu partition on my hard-drive, downloaded it and styled my maps. Documentation on the styling syntax is sometimes a little scarce, but watching their demo video (linked on the main site) answers almost everything. It's possible to do some interesting stuff with nested and/or conditional styles, and some basic CSS understanding should really get you where you want to go.
In the end, TileMill renders a nice, single *.mbtiles file. I don't think there is a way to directly display these in OpenLayers (at least I couldn't find one?), so it was time to use another tool: mbutil. This tool "unzips" the mbtiles-File in to a regular folder structure containing the tiled pngs of my data on the selected zoom levels.
Finally, I uploaded all these files to my FTP-Server, did some heavy reading on OL to get my webmap up and going (you add the created tiles as a TMS layer, but guessing the right source url and layer name took some time and googling) and then burned some hours fiddling around with basic html/CSS issues. I wanted a 100% width/height map with a floating legend following my clients "corporate" (it's a municipality, as mentioned) identity guidelines.
Oh, and so far I use Google Maps as base layers, but that might get replaced soon by some custom aerial pictures served via WMS (not provided by me, but the state's survey and geodata administration).
I hope I didn't forget anything important, but if I did, please feel free to ask! I'll check this thread occasionally.