Eggshells
Eggshells can be used uncomposted and relatively mess-free. These provide calcium to plants. As you use eggs, keep the shells in a gallon ziplock bag in your freezer (so they don't stink). Crush the shells as you go along so you can store more in the bag.
When the bag is really full, spread the shells on a cookie sheet and bake on low heat (160F or so -- the lowest setting in your oven) until they're fully dry. I think I left them in for about 40 minutes last time I did this. This might make your kitchen smell a little funky, but it isn't nearly as bad as when someone microwaves leftover fish in the office break room.
When they're dry, put them in a food processor and puree into a powder. This can give off some dust. I do it outside to keep the kitchen clean. You could probably crush them up small enough manually in the kitchen.
Spread the powder around your plants to provide extra calcium. You can scrape back the mulch and spread it under the mulch if you don't want it to show in your beds. (I put a little scoop of powder in the transplant hole when I set out tomatoes, peppers, and other "hungry" plants, but this won't apply to your perennial garden.)
You could spread larger chunks of shells, but it would get ugly pretty fast. Eggshells don't really break down in any reasonable amount of time.
Wood Ash
If you have a fireplace or wood stove, you can use of wood ash as a fertilizer in your lawn and garden. (Don't use the ash if you burn anything besides firewood; other materials may add contaminants.) Ash will raise your pH, so don't use it if you have alkaline soil already -- and ease up on the lime if you have acid soil that normally requires liming. Ash has varying amounts of nutrients, but 0-1-3 (N-P-K) would be a reasonable guess.
It's also been mentioned in a couple of slugs questions here that you can surround your plants with a thin line of ash to keep slugs off -- apparently they don't like to crawl over it.
Newspaper and Corrugated Cardboard
Black and white (not colored or glossy) newspaper and corrugated cardboard (uncolored and uncoated) can be used as the bottom layers of a sheet mulch for preparing new garden beds. These make decent weed barriers. Be sure to use several sheets of newspaper so that it is thick enough. Be sure to overlap the edges.