The WMS spec does not provide any direction on how a server should implement the GetFeatureInfo response.
In some systems the "pixel tolerance" is a function of the client (web browser or desktop client) - a clicked point can be buffered and the resulting polygon is sent as the query geometry. However, GetFeatureInfo only accepts a point input so that's a dead end.
However, if you scale down the image size in your GetFeatureInfo request, and also scale down the X and Y coordinate of your query, you can effectively increase the pixel tolerance. Consider the following queries based on the Cities layer for the region surrounding Minneapolis/St.Paul:
WMS GetImage, 400 x 400 pixels
If I issue a GetFeatureInfo request at 138, 145 on a 400x400 map gets me Elk River:
WMS GetFeatureInfo, 138,145, 400x400 - gets results
If I re-issue the request at 140, 140 I get no results:
WMS GetFeatureInfo, 140,140, 400x400 - no results
However, if I halve all values and issue the request at 70,70 on a 200x200 map, it works:
WMS GetFeatureInfo, 70,70, 200x200 - gets results
It's extra work to do this sort of viewport adjustment on-the-fly but should do what you want.
For a non-programming (but not FOSS) way you could create a free account and try to upload your image to GIScloud. WMS is one of the outputs you can get fron your project there. Check docs for more information.
For more ambitious way - GeoServer might be good way. I find it easier to interact with than MapServer. Check OpenGeo tutorials for a good starting point.
Best Answer
Depending on how customized your WMS service needs to be I'd start by looking at Geoserver which provides WMS out of the box. It's implemented in Java under the GPL license so may, or may not work for you depending on your requirements.