Peoples' taste varies in every imaginable range so I doubt we can help you to find a good gift for him. Then it also depends on the location and culture, age and your and his personality. (Edit: now I see there is United States in the tags. But even this doesn't tell enough)
I only can tell you my very personal opinion. So please imagine a "it depends very much on lots of things" before any sentences I write.
Do you know other friends of him who can advise you?
What kind of friend is it, where did you meet him the first time, where do you normally meet, what are you doing then? Maybe you can derive a nice gift from these situations or locations.
Is this even an appropriate time to give a gift, given our lack of history?
I'd say a small one is ok. But for me it would be ok if I'd get nothing from a new friend.
If so, what kinds of gifts aren't imposing?
For this small time you know each other I'd say keep it really small. Make it a gesture, nothing else. Get something that doesn't make him think "what the hell shall I do with that" or ask himself why he got it.
For me the only thing that counts in this situation is to show him you are aware of his birthday. Nothing more. Something spontaneous is better than something you thought deep and long. You really are missing history for that.
If you hang out together, invite him to a drink or similar. That's better than pretending to be best friends for years.
Is the monetary value of the gift significant?
No. I don't see a basis for expensive gifts. Don't make him afraid of this new friendship, don't raise expectations that you never intended to raise.