#Preface

This question has a rigorous answer in http://english.stackexchange.com/a/2628/61171 (Credit @CopperKettle for reference.) 

This answer is based on my native AmEng intuition.  It may help some people get a sense of the difference without going into deep grammatical detail.

First, I don't think there's any significant semantic difference between the two sentences.  They are saying exactly the same thing in slightly different ways.

Second, let's simplify by giving ***him*** a name, ***"John"***.  Now we can talk about John directly.  This is simply a teaching aid.

##Grammar Basics

Let's review some basic grammar.

 - ***he*** and ***him*** are pronouns that can be replaced with "John".  
  - I saw John.
  -  I saw him.
  - John saw me.
  - He saw me.
  
 - ***his*** is a possessive pronoun and can be replaced with **`John's`**:
  - John's bike is green.
  - His bike is green.
  - I saw John's bike.
- I saw his bike.
  
Now consider some gerunds in which their function is more clear than the OP's sentences:

 - I saw John dancing.  
 - I saw him dancing.  (I saw him *doing something*.  This conveys a sense of action.)
 - John's dancing is beautiful.
 - His dancing is beautiful.  ("His dancing" is the subject.  I'm talking about his act of dancing, as if it were a static thing.)

____
##Sentence 1 
For the first sentence, *his* is a possessive pronoun.  The following sentences all have a similar feel to them (relative to the "him" sentence):

 - ***I know it without his telling me.***
 - I know it without John's act of telling me.
 - I know it without John's advice.

Here's a tree showing a traditional grammar layout of the sentence:<sup>1</sup>

![enter image description here][1]

Here's a more modern syntax tree:<sup>2</sup>  
![enter image description here][2]















##Second Sentence 

The word "him" is the same as "John", and I think of the phrase as being more active.  John is hypothetically doing something.  Here's a modern syntax tree:<sup>3</sup>


![enter image description here][3]


_____
##Footnotes on Syntax Trees

This section demonstrates how to easily create the images contained within this answer.  As such, this section is only ancillary technical information and is separate from the answer proper.

Below, I show how to generate Labeled Bracket Notation and how to render that notation into an image of a tree.

For the modern grammar syntax trees, I went to the the [Stanford Parser](http://nlp.stanford.edu:8080/parser/index.jsp) and entered the first sentence.  I substituted `[` for `(` and `]` for `)` and plugged that into http://yohasebe.com/rsyntaxtree.  That gave a pretty picture.  I usually resize these in something like pixlr to make them smaller.  These trees use artificial intelligence natural language processing (NLP), and as such, may give less-than-ideal or incorrect results.

##1. Sentence 1 - Traditional Grammar
The first sentence I changed to typify a traditional grammar.

<pre>
[Traditional-Grammar-Sentence
	[Subject I]
	[Predicate 
		[Verb-"know"
			[Verb-Object it]
			[Clause
				[PP 
	    				[P without]
            				[NP
						[N-POS his] 
						[GER-PH^ telling me]
					]
				]
                         ]
                ]
    	 ]
]
</pre>

##2. Sentence 1 - Modern Syntax Tree

The Stanford Parser results for the modern syntax tree didn't express what I wanted, so I modified it slightly.

<pre>
[ROOT
  [S
    [NP [PRP I]]
    [VP [VBP know]
      [NP [PRP it]]
      [PP [IN without]
        [S
          [NP his telling me]
        ]
      ]
    ]
  ]
]
</pre>

##3. Sentence 2 - Modern Syntax Tree

For the second sentence, I liked the Stanford Parser result.  It's still slightly simplified.

<pre>
[ROOT
  [S
    [NP [PRP I]]
    [VP [VBP know]
      [NP [PRP it]]
      [PP [IN without]
        [S
          [NP [PRP him]]
          [VP [VBG telling]
            [NP [PRP me]]]]]]
    ]]
</pre>


  [1]: https://i.sstatic.net/V9gkZ.png
  [2]: https://i.sstatic.net/fjs0V.png
  [3]: https://i.sstatic.net/nCU4O.png